laekov

BZOJ2813 奇妙的Fibonacci

的确比较奇妙。


有一个奇妙的玩意是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);

}


评论

© laekov | Powered by LOFTER