bzoj 2813 奇妙的Fibonacci

#include <cstdio>
#include <bitset>
#include <vector>

using namespace std;

#define DEBUG 0

#define MAXN 3000011
#define MAXC 10000011

typedef long long LL;

const int p = 1000000007;

template <typename T>
void AddMod(T& x, int p) {
    if (x >= p)
        x -= p;
}

//f[i] = the sum of the square of the factors of i
bitset<MAXC> is_prime;
vector<int> prime;
void get(int sum2[], int num[], int n, int p) {
    static int pk[MAXC];
    is_prime.set();
    prime.clear();
    sum2[1] = 1;
    num[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            prime.push_back(i);
            pk[i] = i;
            sum2[i] = ((LL)i * i + 1) % p;
            num[i] = 2;
        }
        for (int pr : prime) {
            int now = i * pr;
            if (now > n) break;
            is_prime[now] = false;
            if (i % pr == 0) {  //pr is the minimum prime factor of i
                pk[now] = pk[i] * pr;
                sum2[now] = (sum2[i] + (LL)sum2[i / pk[i]] * pk[now] % p * pk[now]) % p;
                num[now] = num[i] + num[i / pk[i]];
                break;
            } else {
                pk[now] = pr;
                sum2[now] = (1 + (LL)pk[now] * pk[now]) % p * sum2[i] % p;
                num[now] = num[i] << 1;
            }
        }
    }
}

int main() {
    static int sum2[MAXC], num[MAXC];

    get(sum2, num, MAXC - 1, p);
    for (int i = 1; i < MAXC; i += 2) {
        ++num[i];
        AddMod(sum2[i] += 4, p);
    }

    int q;
    static int qs[MAXN], a, b, c;
    scanf("%d%d%d%d%d", &q, qs + 1, &a, &b, &c);
    for (int i = 2; i <= q; ++i) {
        qs[i] = ((LL)qs[i-1] * a + b) % c + 1;
    }
#if DEBUG
    for (int i = 1; i <= q; ++i) {
        printf("%d ", qs[i]);
    }
    putchar('\n');
#endif
    int sa = 0, sb = 0;
    for (int i = 1; i <= q; ++i) {
        AddMod(sa += num[qs[i]], p);
        AddMod(sb += sum2[qs[i]], p);
    }
    printf("%d\n%d\n", sa, sb);

    return 0;
}