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 le 3*10^6，C le10^7，A le10^7，B le10^7，1 le Q1le C $
Solution
首先还是要找规律。发现(f_j|f_iLeftrightarrow j|i)。
对于任意一个质数(p)，我们在模(f_p)的意义下观察一些斐波那契数列：
斐波那契数列会每(p)项分成一段，其中第(i)段是(f_{p-1}^{i-1}f_{1..p})。
由于(f_{p-1})与(f_p)互质，因此(f_{p-1}^{i-1})都与(f_p)互质。既然第一段只能在第(p)项，也就是该段最后一项取0，那么之后的每一段都只能在最后一项取0.
也就是说(f_p)整除哪一些(f_i)呢？恰好是那些(p|i)的(f_i)。
那么对于任意整数(j)，(f_j)整除哪一些(f_i)呢？把(j)质因数分解(j=p_1^{q_1}p_2^{q_2}...p_m^{q_m})，可知(f_{p_k}|f_j)（(kin[1,m])）。当且仅当(f_{p_k}|f_i)（(kin[1,m])）时，有(f_j|f_i)，而此时(p_k|i)（(kin[1,m])）。
故证毕：对于任意正整数(i)和(j)，有(f_j|f_iLeftrightarrow j|i)。
所以本题相当于询问(q)的因数个数、因数平方和，是线性筛的基本应用。因数平方和的表达式是
记录每个数的最小质因子的幂、除尽最小质因子的数(nop)就可以计算了。我第一次写的代码使用了快速幂计算(i\%p==0)时的累加，然而不必要，对(sigma^2(i))乘上(p^2)就可以把最小质因子处的(sum)整体偏移，括号里需要加上的1，対整体加上(sigma^2(nop[i]))即可。
注意回答询问时，不可直接输出上述统计的东西。(f_2=1)非常特殊，当询问(q)为偶数时，因为(2|q)，所以2会被统计到，且2本来就需要统计，因为(f_2|f_q)是合法的的。但是当询问(q)为奇数时，(2
mid q)，所以2未被统计，但从原题意义上看，依然有(f_2|f_q)，2应该被统计。所以(q)是奇数时，第一问要加上1，第二问要加上4（(2^2=4)）。
我脑残，都加上了1，居然还有50......说明那些数据模数神奇，询问都是偶数。
Code
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=10000001,MOD=1e9+7;
bool vis[N];
int p[N],pcnt,sigma0[N],minpq[N];
ll nop[N],sigma2[N];
ll ans1,ans2;
void sieve(){
sigma0[1]=1; sigma2[1]=1;
for(int i=2;i<N;i++){
if(!vis[i]){
p[++pcnt]=i;
sigma0[i]=2;
sigma2[i]=(1LL*i*i+1)%MOD;
minpq[i]=1;
nop[i]=1;
}
for(int j=1;j<=pcnt&&i*p[j]<N;j++){
int x=i*p[j];
vis[x]=true;
if(i%p[j]==0){
minpq[x]=minpq[i]+1;
nop[x]=nop[i];
sigma0[x]=sigma0[i]/(minpq[i]+1)*(minpq[x]+1);
sigma2[x]=(sigma2[i]*(1LL*p[j]*p[j]%MOD)%MOD+sigma2[nop[i]])%MOD;
break;
}
sigma0[x]=sigma0[i]*sigma0[p[j]];
sigma2[x]=sigma2[i]*sigma2[p[j]]%MOD;
minpq[x]=1;
nop[x]=i;
}
}
}
int main(){
sieve();
int n,q,qlast=0,a,b,c;
scanf("%d%d%d%d%d",&n,&q,&a,&b,&c);
for(int i=1;i<=n;i++){
if(i>1) q=(1LL*qlast*a+b)%c+1;
qlast=q;
ans1+=sigma0[q]+(q&1);
(ans2+=sigma2[q]+4*(q&1))%=MOD;
}
printf("%lld
%lld
",ans1,ans2);
return 0;
}