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
Sol
首先我们有((F_i,F_j)=F_{(i,j)})我不会证qwq
我们钦定(F_i)之后，如果((F_i,F_j)=F_j)那么(F_j)就能够整除(F_i)。
等价于((i,j)=j)
显然(i)的约数全部满足这一性质。
所以我们实际要求的是每个数字的约数个数和和约数平方和。
我们设e[i]为i的最小质因数次数，d[i]为i除去最小质因子之后的商，g[i]为i的约数个数，f[i]为i的约数平方和 。
那么在线性筛时：
质数：e[i]=1,d[i]=1,g[i]=2,f[i]=i^2+1;
记k=i*pri[j]；
i%pri[j]==0：e[k]=e[i]+1,d[k]=d[i],g[k]=g[i]/(e[i]+1)*(e[k]+1),f[k]=f[i]*pri[j]^2+f[d[i]];
i%pri[j]!=0：e[k]=1,d[k]=i,g[k]=g[i]*2,f[k]=f[i]*(pri[j]^2+1);
e,d,g的表达式很好理解，f的第一个式子含义是把这个质因子次数+1时，除了这个最小质因子以外的因子平方和都不变，新产生的因数的平方和要乘以这个质因子。f的第二个式子含义是新产生的因数的平方和加上原来的平方和。
要注意f[2]=1，所以如果x是奇数，没有算入贡献，要特判。
Code
#include <cstdio>
int i,T,x,a,b,c,t,d[10000005],e[10000005],f[10000005],g[10000005],p[10000005],v[10000005],sg,sf,P=1000000007;
int main()
{
for(g[1]=f[1]=1,i=2;i<=10000000;i++)
{
if(!v[i]){p[++t]=i;e[i]=d[i]=1;g[i]=2;f[i]=(1ll*i*i+1)%P;}
for(int j=1,k;j<=t&&(k=i*p[j])<=10000000;j++)
{
v[k]=1;
if(i%p[j]==0)
{
e[k]=e[i]+1;g[k]=g[i]/(e[i]+1)*(e[k]+1);d[k]=d[i];f[k]=(1ll*f[i]*p[j]%P*p[j]%P+f[d[i]])%P;
break;
}
else e[k]=1,d[k]=i,g[k]=g[i]<<1,f[k]=f[i]*(1ll*p[j]*p[j]%P+1)%P;
}
}
for(scanf("%d%d%d%d%d",&T,&x,&a,&b,&c),a%=c,b%=c;T--;x=(1ll*x*a+b)%c+1)
{
sg+=g[x]+(x&1);sf+=f[x]+4*(x&1);
if(sg>=P) sg-=P;if(sf>=P) sf-=P;
}
printf("%d
%d
",sg,sf);
}