莫比乌斯繁衍1

bzoj crash的数字表格 2154

题目大意

n , m <= 10^7

终于会正经的莫比乌斯繁衍了。就是包含两种变换1.莫比乌斯繁衍、莫比乌斯变换 2.考虑贡献（被计算的次数），进行枚举顺序的变化，从而达到线性筛的目的。

因为过程太繁琐，用图片替代输入

减少取模次数有奇效，不知道为什么如此慢

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define maxn 10000020
 7 #define mod 20101009
 8 
 9 int prime[maxn],cnt;
10 long long f[maxn];
11 bool tag[maxn];
12 long long n,m,ans;
13 
14 void init(){
15     f[1] = 1;
16     for (register int i = 2 ; i <= n ; i++){
17         if ( !tag[i] ) prime[++cnt] = i , f[i] = 1 - i;
18         for (register int j = 1 ; j <= cnt && prime[j] * i <= n ; j++){
19             tag[i * prime[j]] = 1;
20             if ( (i % prime[j]) == 0 ){
21                 f[i * prime[j]] = f[i];
22                 break;
23             }
24             else{
25                 f[i * prime[j]] = (f[i] * (long long) (1 - prime[j]));
26             }
27         }
28     }
29     for (register long long i = 1 ; i <= n ; i++) f[i] = (f[i] * i);
30     for (register int i = 2 ; i <= n ; i++) f[i] = (f[i] + f[i - 1]) % mod;
31 }
32 inline long long power(long long x,long long y){
33     long long res = 1;
34     while ( y ) {
35         if ( y & 1 ) res = (res * x) % mod;
36         x = (x * x) % mod;
37         y >>= 1;
38     }
39     return res % mod;
40 }
41 int main(){
42     freopen("input.txt","r",stdin);
43     scanf("%lld %lld",&n,&m);
44     if ( n > m ) swap(n,m);
45     init();
46     for (register long long i = 1 ; i <= min(n,m) ;){
47         long long next = min(n/(n/i),m/(m/i));
48         ans = (ans + (((f[next] - f[i - 1]) + mod) % mod * (n/i) % mod * (m/i) % mod * (n/i + 1) % mod * (m/i + 1) % mod)) % mod;
49         i = next + 1;
50     }
51     ans = (ans * power(4,mod - 2)) % mod;
52     printf("%d
",(int)((ans % mod + mod) % mod));
53 }