—————————数学|BZOJ 2813: 奇妙的Fibonacci 线性筛 —————————数学|数论

2813: 奇妙的Fibonacci Time Limit: 20 SecMemory Limit: 512 MB
Submit: 536Solved: 152
[Submit][Status][Discuss] Description
Fibonacci数列是这样一个数列： F1 = 1， F2 = 1， F3 = 2 . . . Fi = Fi-1 + Fi-2 (当 i >= 3) pty忽然对这个古老的数列产生了浓厚的兴趣，他想知道：对于某一个Fibonacci数Fi，有多少个Fj能够整除Fi (i可以等于j)，他还想知道所有j的平方之和是多少。
Input 第一行一个整数Q,表示Q个询问。
第二行四个整数:Q1, A, B, C
第i个询问Qi = (Qi-1 * A + B) mod C + 1(当i >= 2)

Output Ai代表第i个询问有多少个Fj能够整除FQi。
Bi代表第i个询问所有j的平方之和。
输出包括两行：
第一行是所有的Ai之和。
第二行是所有的Bi之和。
由于答案过大，只需要输出除以1000000007得到的余数即可。

Sample Input 2
2 2 1 8

Sample Output 6
55
HINT
对于100%的数据保证：Q <= 3*10^6，C <= 10^7，A <= 10^7，B <= 10^7，1 <= Q1<= C

证明有很多。。不看题解我不会
所以。。。
线性筛约数个数，平方和

#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar(); } while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return f*x; } const int N=10001000; const ll mod=1000000007; ll n,x,a,b,c; int prime[N],cnt,mn[N],cot[N],ci[N],sqr[N]; //sqr ??êy??·?cot ??êy??êyci ×?D??êòò×ó′?êymn3yè￥×?D??êòò×óμ???êy bool book[N]; void initial() { sqr[1]=1; cot[1]=1; for(int i=2; i<=N; i++) { if(!book[i]) { prime[++cnt]=i; mn[i]=ci[i]=1; cot[i]=2; sqr[i]=(1ll*i*i+1)%mod; } for(int j=1; j<=cnt&&prime[j]*i<=N; j++) { book[i*prime[j]]=1; mn[prime[j]*i]=i; ci[prime[j]*i]=1; cot[prime[j]*i]=cot[i]<<1; sqr[prime[j]*i]=(1ll*sqr[i]*prime[j]*prime[j]+sqr[i])%mod; if(i%prime[j]==0) { mn[prime[j]*i]=mn[i]; ci[prime[j]*i]=ci[i]+1; cot[prime[j]*i]=cot[i]/ci[prime[j]*i]*(ci[prime[j]*i]+1); sqr[prime[j]*i]=(1ll*sqr[i]*prime[j]*prime[j]+sqr[mn[i]])%mod; break; } } } } int main() { initial(); n=read(); x=read(); a=read(); b=read(); c=read(); a%=c; b%=c; int ans1=0,ans2=0; for(int i=1; i<=n; i++) { if(i!=1)x=(x*a+b)%c+1; ans1+=(cot[x]+(x&1)); ans2+=(sqr[x]+(x&1)*4); ans1%=mod; ans2%=mod; } printf("%d\n%d\n",ans1,ans2); return 0; } /* 2 2218 6 55 */

【—————————数学|BZOJ 2813: 奇妙的Fibonacci 线性筛】