关键词：
http://acm.hdu.edu.cn/showproblem.php?pid=6069
题目大意：求 i 从 l 到 r 中 i 的k次方的因子数之和。
解题思路：我们可以知道一个数有因子，则这个数的因子一定是若干个质数因子排列组合得到的。我们首先要得到10^6中的素数，然后它的因子数量是 相同质因子数量+1 的乘积，所以我们能够想到从 l 到 r 枚举每一个i得到其 相同质因子数量+1 的乘积 的累加和。但是这样在枚举时会发现有一些质数是并不是所求的 i 的因子，所以我们应该反过来考虑，对于每一个质因子找出 l 到 r 中它的倍数，这样时间就被缩短了。
AC代码：
1 #include <iostream> 2 #include <bits/stdc++.h> 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 ",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 ",in[i],l+i,tmp[i]); 66 ans=(ans+tmp[i])%SMod; 67 //printf("%lld ",ans); 68 } 69 printf("%lld ",ans); 70 } 71 return 0; 72 }
这个代码挺奇怪的我感觉都对，但是15个数据过了14个就倒数第二个错了郁闷啊>_<||| 。
求大神指点一下
1 #include <iostream> 2 #include <bits/stdc++.h> 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 ",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]<i+l) 73 tmp[i]=tmp[i]*(k+1); 74 //printf("%lld %lld %lld ",in[i],l+i,tmp[i]); 75 if(l+i==1) 76 { 77 ans=(ans+1)%SMod; 78 } 79 else if(tmp[i]==1) 80 { 81 ans=(ans+2)%SMod; 82 } 83 else 84 { 85 ans=(ans+tmp[i])%SMod; 86 } 87 } 88 printf("%lld ",ans); 89 } 90 return 0; 91 }
hdu6069countingdivisors欧拉筛法(代码片段)
CountingDivisorsTimeLimit:10000/5000MS(Java/Others)MemoryLimit:524288/524288K(Java/Others)TotalSubmission(s):6208AcceptedSubmission(s):2147ProblemDescriptionInmathematics,thefunctiond(n)denotesthenumb 查看详情
hdu6069countingdivisors
题意：给出求L,R之间的数的K次方的因子数之和 思路：打表求出1~10^6之间的素数，枚举[L,R]之间素数的倍数，然后按算数基本定理求出因子个数和。处理过后[L,R]之间的数要么是1，要么是一个素数，再次根据算数基本定理计算... 查看详情
hdu6069多校countingdivisors
思路：对于n^k其实就是每个因子的个数乘了一个K。然后现在就变成了求每个数的每个质因子有多少个，但是比赛的时候只想到sqrt(n)的分解方法，总复杂度爆炸，就一直没过去，然后赛后看官方题解感觉好妙啊！通过... 查看详情
hdu6069countingdivisors——2017multi-universitytraining4
CountingDivisorsTimeLimit:10000/5000MS(Java/Others) MemoryLimit:524288/524288K(Java/Others)TotalSubmission(s):2599 AcceptedSubmission(s):959ProblemDescrip 查看详情
hdu6069countingdivisors（唯一分解定理+因子数）
http://acm.hdu.edu.cn/showproblem.php?pid=6069题意： 思路：根据唯一分解定理，$n={a_{1}}^{p1}*{a2_{}}^{p2}...*{a_{m}}^{pm}$，那么n的因子数就是n的k次方也是一样的，也就是p前面乘个k就可以了。先打个1e6范围的素数表，然后枚举每个素数，在... 查看详情
区间筛2-17多校训练四hdu6069countingdivisors
http://acm.hdu.edu.cn/showproblem.php?pid=6069【题意】给定l,r,k，求d(n)是n的因子个数【思路】【Accepted】1#include<iostream>2#include<cstdio>3#include<cstring>4#include<string>5#include<cmath> 查看详情
hdu6069countingdivisors
//变量命名很重要你看我抄队友的代码抄一遍就t了再改还是t我以为是我不够大力原来是这个变量名弄的太混乱了--搞了好半天才发现哈哈 //有一个很重要的定理是一个数的因数个数和他的素数幂次乘积表达式的关系哈哈当时... 查看详情
hdu6069countingdivisors（区间素数筛法）
题意：。。。就题面一句话思路：比赛一看公式，就想到要用到约数个数定理约数个数定理就是：对于一个大于1正整数n可以分解质因数：则n的正约数的个数就是对于n^k其实就是每个因子的个数乘了一个K然后现在就变成了求每... 查看详情
countingdivisorshdu-6069
CountingDivisors HDU-6069 题意：给定区间[a,b]和k，求xk有多少因子（x属于[a,b]），求和。题解：http://blog.csdn.net/zlh_hhhh/article/details/76680641a、b最大可达到1e12，但是b-a<1e6。一开始愚蠢的一个一个分解然后去求有多少因子然后求... 查看详情
hdu多校第四场1005didn‘tisaytomakemyabilitiesaverageinthenextlife?!单调栈+莫队(代码片段)
原题链接：https://acm.hdu.edu.cn/showproblem.php?pid=6989题意给你一个数列，定义一个区间的平均值为(Max+Min)/2，询问一个区间的所有平均值的期望是多少。分析我们把题目的式子化简一下，就是∑max+∑min2∗len∗(... 查看详情
杭电2018多校第四场(2018multi-universitytrainingcontest4)1005.probleme.matrixfromarrays(hdu6336)-(代码片段)
6336.ProblemE.MatrixfromArrays 不想解释了，直接官方题解: 队友写了博客，我是水的他的代码------>HDU6336子矩阵求和 至于为什么是4倍的，因为这个矩阵是左上半边有数，所以开4倍才能保证求的矩阵区域里面有数... 查看详情
hdu6069
CountingDivisorsProblemDescriptionInmathematics,thefunction d(n) denotesthenumberofdivisorsofpositiveinteger n.Forexample, d(12)=6 because 1,2,3,4,6,12 areall 1 查看详情
hdu6069[素数筛法]2017多校3
/*hdu6069[素数筛法]2017多校3*/#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;LLl,r,k;constLLMOD=998244353LL;intT,n,prime[1100000],primesize;boolisprime[11000000];voidgetlist(intlistsize){m 查看详情
2018年全国多校算法寒假训练营练习比赛（第四场）题解
【题目链接】 A-石油采集题意：有一个$01$矩阵，每次可以拿走两个相邻的$1$，问最多能操作几次。这题和HDU1507一样。二维矩阵四连通图是一个二分图，题目的操作事实上就是求这个二分图的最大匹配。 B-道路建设最... 查看详情
hdu6069
思路：n=p1^x1*p2^x2....pm^xm，则p的约数个数为(x1+1)*(x2+1)....(xm+1)，那么n^k=p1^(x1+k)....pm^(xm+k),约数个数为(x1*k+1)*....*(xm*k+1)。 先求出1-1e6内的质数，再对l--r之间的数求xi1#include<bits/stdc++.h>2usingnamespacestd;3typedef 查看详情
hdu6069(简单数学+区间素数晒法)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6069 题意:给出l,r,k．求：(lambdad(i^k))mod998244353，其中l<=i<=r,d(i)为i的因子个数． 思路：若x分解成质因子乘积的形式为x=p1^a1*p2^a2*...*pn^an，那么d(x)=(a1+1)*(a2+1)*...*(an 查看详情
hdu6069,2017多校1003
这是一道区间素数筛的题目，首先线性筛出1e6的素数,然后用每一个素数对区间内的数进行素数分解公式:求某个数的因子个数，先进行素数分解x=p1^z1*p2^z2*p3^z3;然后sum=(z1+1)*(z2+1）*(z3+1);1#include<cstdio>2typedeflonglongll;3constintN=100001... 查看详情
probleme.matrixfromarrays（杭电2018年多校第四场+思维+打表找循环节）(代码片段)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6336题目：题意：给你一个l个元素的数组a，用题目中的程序构造一个新的矩阵，询问q次，问以（x1,y1)为左上角，（x2，y2）为右下角的矩阵内的元素之和（原点在左上角）。思路：我们... 查看详情