题目大意：求 i 从 l 到 r 中 i 的k次方的因子数之和。
解题思路：我们可以知道一个数有因子，则这个数的因子一定是若干个质数因子排列组合得到的。我们首先要得到10^6中的素数，然后它的因子数量是 相同质因子数量+1 的乘积，所以我们能够想到从 l 到 r 枚举每一个i得到其 相同质因子数量+1 的乘积 的累加和。但是这样在枚举时会发现有一些质数是并不是所求的 i 的因子，所以我们应该反过来考虑，对于每一个质因子找出 l 到 r 中它的倍数，这样时间就被缩短了。
AC代码：
1 #include2 #include 3 using namespace std; 4 const int maxn=1100000; 5 const long long SMod=998244353; 6 bool is_prime[maxn+1]; 7 long long prime[maxn],tmp[maxn],in[maxn]; 8 int sieve(int n) 9 {10 int p=0;11 for(int i=0; i<=n; i++) is_prime[i]=true;12 is_prime[0]=is_prime[1]=false;13 for(int i=2; i<=n; i++)14 {15 if(is_prime[i])16 {17 prime[p++]=i;18 for(int j=2*i; j<=n; j=j+i)19 is_prime[j]=false;20 }21 }22 return p;23 }24 int main()25 {26 sieve(1000007);27 // for(int i=0;i<10;i++)28 // printf("%d\n",prime[i]);29 //freopen("1003.in","r",stdin);30 //freopen("out.txt","w",stdout);31 int t;32 long long l,r,k,ans,cnt,num;33 scanf("%d",&t);34 while(t--)35 {36 scanf("%lld%lld%lld",&l,&r,&k);37 int len=r-l;38 for(int i=0; i<=len; i++)39 {40 tmp[i]=1;41 in[i]=i+l;42 }43 ans=0;44 num=0;45 for(int i=0; prime[i]*prime[i]<=r&&i<78498; i++)46 {47 int p=prime[i];48 for(int j=l/p*p-l; j<=len; j+=p)49 {50 if(j<0)51 continue;52 num=0;53 while(in[j]%p==0)54 {55 num++;56 in[j]=in[j]/p;57 }58 tmp[j]=(tmp[j]*(((num*k)%SMod)+1))%SMod;59 }60 }61 for(int i=0; i<=len; i++)62 {63 if(in[i]>1)64 tmp[i]=(tmp[i]*(k+1))%SMod;65 //printf("%lld %lld %lld\n",in[i],l+i,tmp[i]);66 ans=(ans+tmp[i])%SMod;67 //printf("%lld\n",ans);68 }69 printf("%lld\n",ans);70 }71 return 0;72 }
这个代码挺奇怪的我感觉都对，但是15个数据过了14个就倒数第二个错了郁闷啊>_<||| 。
求大神指点一下
1 #include2 #include 3 using namespace std; 4 const int maxn=1100000; 5 const long long SMod=998244353; 6 bool is_prime[maxn+1]; 7 long long prime[maxn],tmp[maxn],in[maxn]; 8 int sieve(int n) 9 {10 int p=0;11 for(int i=0; i<=n; i++) is_prime[i]=true;12 is_prime[0]=is_prime[1]=false;13 for(int i=2; i<=n; i++)14 {15 if(is_prime[i])16 {17 prime[p++]=i;18 for(int j=2*i; j<=n; j=j+i)19 is_prime[j]=false;20 }21 }22 return p;23 }24 int main()25 {26 sieve(1000007);27 // for(int i=0;i<10;i++)28 // printf("%d\n",prime[i]);29 //freopen("1003.in","r",stdin);30 //freopen("out.txt","w",stdout);31 int t;32 long long l,r,k,ans,cnt,num;33 scanf("%d",&t);34 while(t--)35 {36 scanf("%lld%lld%lld",&l,&r,&k);37 int len=r-l;38 for(int i=0; i<=len; i++)39 {40 tmp[i]=1;41 in[i]=1;42 }43 ans=0;44 num=0;45 for(int i=0; prime[i]*prime[i]<=r&&i<78498; i++)46 {47 int p=prime[i];48 int it=prime[i]-(l%prime[i]);49 if(it==prime[i])50 it=0;51 if(it>len)52 continue;53 for(int j=it; j<=len;)54 {55 long long data=j+l;56 while(data%p==0)57 {58 num++;59 data=data/p;60 in[j]=in[j]*p;61 }62 if(num!=0)63 {64 tmp[j]=(tmp[j]*(((num*k)%SMod)+1))%SMod;65 num=0;66 }67 j=j+p;68 }69 }70 for(int i=0; i<=len; i++)71 {72 if(in[i]*in[i]
