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

解法：膜唐老师。http://blog.csdn.net/skywalkert/article/details/43970131

///BZOJ 2813

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 10000010;
const int mod = 1000000007;
int cnt, prime[maxn], e[maxn], d[maxn], g[maxn], f[maxn];
int sumg, sumf;
bool mark[maxn];

///e[i]为i的最小质因数次数，d[i]为i除去最小质因数的数，g[i]为i的因数个数，f[i]为i的因数平方和

int main()
{
    int Q, q, A, B, C;
    scanf("%d%d%d%d%d", &Q,&q,&A,&B,&C);
    A%=C, B%=C;
    g[1] = f[1] = 1;
    for(int i=2; i<=C; i++){
        if(!mark[i]){
            prime[cnt++] = i;
            e[i] = d[i] = 1;
            g[i] = 2;
            f[i] = ((LL)i*i+1)%mod;
        }
        for(int j=0, k; j<cnt&&(k=i*prime[j]) <= C; j++){
            mark[k] = 1;
            if(i%prime[j]==0){
                e[k] = e[i]+1;
                g[k] = (g[i] / (e[i]+1)) * (e[k]+1);
                d[k] = d[i];
                f[k] = (f[i] * ((LL)prime[j] * prime[j] % mod) + f[d[i]]) % mod;
                break;
            }
            else{
                e[k] = 1;
                d[k] = i;
                g[k] = g[i] << 1;
                f[k] = f[i] * (((LL)prime[j]*prime[j] + 1) % mod) % mod;
            }
        }
    }
    while(Q--)
    {
        sumg += g[q] + (q & 1);
        sumf += f[q] + 4 * (q & 1);
        if(sumg >= mod) sumg -= mod;
        if(sumf >= mod) sumf -= mod;
        q = (q * (LL)A + B) % C + 1;
    }
    printf("%d\n%d\n", sumg, sumf);
    return 0;
}