bzoj 2813 奇妙的Fibonacci

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 <cstdio>
#include <algorithm>
using namespace std;
const int N = 10000000, mod = 1000000007;
bool p[N + 10];
int n, T, a, b, c, t[N + 10], pr[N + 10];
long long k, ans1, ans2, d[N + 10], r[N + 10], g[N + 10];
void init(int n) {
    r[1] = d[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!p[i])
            pr[++pr[0]] = i, d[i] = 2, t[i] = g[i] = 1,
            r[i] = (1ll * i * i + 1ll) % mod;
        for (int j = 1; j <= pr[0] && i * pr[j] <= n; ++j) {
            p[i * pr[j]] = 1;
            if (i % pr[j] == 0) {
                d[i * pr[j]] = (1ll * d[i] / (t[i] + 1ll) * (t[i] + 2ll)) % mod;
                t[i * pr[j]] = t[i] + 1;
                g[i * pr[j]] = g[i];
                r[i * pr[j]] = (r[g[i]] + 1ll * r[i] * pr[j] % mod * pr[j] % mod) % mod;
                break;
            }
            d[i * pr[j]] = d[i] * d[pr[j]];
            t[i * pr[j]] = 1;
            g[i * pr[j]] = i % mod;
            r[i * pr[j]] = (r[i] + 1ll * r[i] * pr[j] % mod * pr[j] % mod) % mod;
        }
    }
}
main() {
    scanf("%d%d%d%d%d", &T, &n, &a, &b, &c);
    init(c);
    while (T--) {
        long long tmp;
        tmp = d[n] + ((n & 1) ? 1 : 0);
        ans1 = (ans1 + tmp) % mod;
        tmp = r[n] + ((n & 1) ? 4 : 0);
        ans2 = (ans2 + tmp) % mod;
        n = (1ll * n * a + b) % c + 1;
    }
    printf("%lld\n%lld\n", ans1, ans2);
}