的确比较奇妙。
有一个奇妙的玩意是fib[gcd(i, j)] == gcd(fib[i], fib[j])。(fib[1] = fib[2] = 1)
然后就比较可搞了。
线性筛处理每个数的因子个数和因子和。开一点变量然后推一下就出来了。
然后要注意fib[2]也可以整除所有奇数，包括1。表示在这上面坑了2次提交。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define _l (long long int)
const int maxn = 10000009;
const int mod = 1000000007;
int tp, pn[maxn], sa[maxn], sb[maxn], b[maxn], c[maxn];
bool pr[maxn];
void pre(int n) {
memset(pr, 0, sizeof(pr));
tp = 0;
sa[1] = 1;
sb[1] = 1;
b[1] = 1;
c[1] = 0;
for (int i = 2; i <= n; ++ i) {
if (!pr[i]) {
pn[tp ++] = i;
sa[i] = 2;
sb[i] = (_l i * i + 1) % mod;
b[i] = 1;
c[i] = 1;
}
for (int j = 0, v; j < tp && i * pn[j] <= n; ++ j) {
v = i * pn[j];
pr[v] = 1;
if (i % pn[j]) {
sa[v] = sa[i] * 2;
sb[v] = _l sb[i] * ((_l pn[j] * pn[j] + 1) % mod) % mod;
b[v] = i;
c[v] = 1;
}
else {
sa[v] = sa[i] / (c[i] + 1) * (c[i] + 2);
//int vn = v / b[i];
//sb[v] = (sb[i] + _l sb[b[i]] * vn % mod * vn % mod) % mod;
sb[v] = (_l sb[i] * pn[j] % mod * pn[j] + sb[b[i]]) % mod;
b[v] = b[i];
c[v] = c[i] + 1;
break;
}
}
}
for (int i = 1; i <= n; i += 2) {
sa[i] = (sa[i] + 1) % mod;
sb[i] = (sb[i] + 4) % mod;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
int n, q, a, b, c, ansa, ansb;
scanf("%d%d%d%d%d", &n, &q, &a, &b, &c);
a %= c;
b %= c;
pre(c);
ansa = ansb = 0;
while (n --) {
ansa = (ansa + sa[q]) % mod;
ansb = (ansb + sb[q]) % mod;
q = (_l q * a + b) % c + 1;
}
printf("%d\n%d\n", ansa, ansb);
}