LOJ#2085 循环之美

佚名 6年前 (2019-04-24) 随笔 1231人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

解：首先看这个纯循环到底是什么玩意.....

经过一番打表，发现纯循环小数就是分母与进制互质的既约分数。

 1 #include <bits/stdc++.h>
 2 
 3 std::bitset<1001> vis;
 4 
 5 inline bool check(int x, int y) { /// x / y
 6     //printf("x = %d y = %d \n", x, y);
 7     vis.reset();
 8     int rest = x % y;
 9     if(!rest) return true;
10     int op = rest;
11     vis[op] = 1;
12     //printf("op = %d \n", op);
13     while(true) {
14         rest *= 10;
15         int r = rest % y;
16         //printf("r  = %d \n", r);
17         if(vis[r]) {
18             //printf("return %d = %d \n", r, op);
19             return r == op;
20         }
21         vis[r] = 1;
22         rest = r;
23     }
24     return false;
25 }
26 
27 int gcd(int a, int b) {
28     if(!b) return a;
29     return gcd(b, a % b);
30 }
31 
32 int main() {
33 
34     int n;
35     scanf("%d", &n);
36 
37     for(int i = 0; i <= n; i++) {
38         for(int j = 1; j <= n; j++) {
39             if(gcd(i, j) == 1) printf("%d ", (int)check(i, j));
40             else printf("  ");
41         }
42         puts("");
43     }
44 
45     return 0;
46 }

打表程序

那么就有了一个很显然的O(nmlogV)的做法...直接暴力枚举然后检验。实测24分。

 1 #include <bits/stdc++.h>
 2 
 3 int gcd(int a, int b) {
 4     if(!b) return a;
 5     return gcd(b, a % b);
 6 }
 7 
 8 int main() {
 9     int n, m, k, ans = 0;
10     scanf("%d%d%d", &n, &m, &k);
11     if(1ll * n * m > 1000000000) return 0;
12     for(int i = 1; i <= m; i++) {
13         if(gcd(k, i) > 1) continue;
14         for(int j = 1; j <= n; j++) {
15             ans += gcd(i, j) == 1;
16         }
17     }
18     printf("%d\n", ans);
19     return 0;
20 }

24分暴力

然后发现最里面那句话有点像phi...仔细思考之后发现不是。

现在开始鬼畜时间...推柿子。

其中有两步转化，分别是把[x=1]用∑μ代替和把[1=(id,k)]用[1=(i,k)][1=(d,k)]代替。

于是考虑最后这个式子，发现有个东西[1=(a,k)]，于是设这个东西为g(x)，它的前缀和为f(x)。又令F为μ·g的前缀和。

那么答案就是下式：

这个东西显然可以分块一波。后两项可以O(1)算，前面的可以线性预处理。于是我们有个O(n)的算法。可以获得84分。

 1 #include <bits/stdc++.h>
 2 
 3 typedef long long LL;
 4 const int N = 20000010;
 5 
 6 int miu[N], p[N], top, f[N], phi[N], n, m, k, F[N];
 7 bool vis[N];
 8 
 9 inline void getp(int n) {
10     phi[1] = miu[1] = 1;
11     for(int i = 2; i <= n; i++) {
12         if(!vis[i]) {
13             p[++top] = i;
14             miu[i] = -1;
15             phi[i] = i - 1;
16         }
17         for(int j = 1; j <= top && i * p[j] <= n; j++) {
18             vis[i * p[j]] = 1;
19             if(i % p[j] == 0) {
20                 //miu[i * p[j]] = 0;
21                 phi[i * p[j]] = phi[i] * p[j];
22                 break;
23             }
24             phi[i * p[j]] = phi[i] * (p[j] - 1);
25             miu[i * p[j]] = -miu[i];
26         }
27     }
28     return;
29 }
30 
31 int gcd(int a, int b) {
32     if(!b) return a;
33     return gcd(b, a % b);
34 }
35 
36 inline void prework() {
37     for(int i = 1; i <= k; i++) {
38         f[i] = f[i - 1] + (gcd(i, k) == 1);
39         F[i] = F[i - 1] + (f[i] - f[i - 1]) * miu[i];
40     }
41     int len = std::min(n, m);
42     for(int i = k + 1; i <= len; i++) {
43         f[i] = f[k] * (i / k) + f[i % k];
44         F[i] = F[i - 1] + (f[i] - f[i - 1]) * miu[i];
45     }
46     return;
47 }
48 
49 inline int getf(int x) {
50     if(x <= k) return f[x];
51     return f[k] * (x / k) + f[x % k];
52 }
53 
54 int main() {
55     LL ans = 0;
56     scanf("%d%d%d", &n, &m, &k);
57     if(1ll * n * m < 1e9) {
58         for(int i = 1; i <= m; i++) {
59             if(gcd(k, i) > 1) continue;
60             for(int j = 1; j <= n; j++) {
61                 ans += gcd(i, j) == 1;
62             }
63         }
64         printf("%lld\n", ans);
65         return 0;
66     }
67     if(n < N) {
68         getp(n);
69         prework();
70         int len = std::min(n, m);
71         for(int i = 1, j; i <= len; i = j + 1) {
72             j = std::min(n / (n / i), m / (m / i));
73             /// [i, j]
74             ans += 1ll * (F[j] - F[i - 1]) * (n / i) * getf(m / i);
75         }
76         printf("%lld\n", ans);
77     }
78     return 0;
79 }