E - Madoka and The Best University（数论/欧拉函数）

题目
参考

题意

给定正数n，求$\sum lcm(c,gcd(a,b)),a+b+c=n,1<=a,b,c$

思路

暴力枚举c，对于固定的c，a+b=n-c
因为gcd(a,b)=gcd(a,a+b)=gcd(a,n-c)
枚举n-c的所有因子d，对于固定的d
有d=gcd(a,b)=gcd(a,n-c),d|n，要求满足能被d整除且与n-c互素的a的个数，
实际上，就是欧拉值$\varphi (n-c/d)$。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100010;
const int mod = 1e9 + 7;

int n;

int phi[maxn]; // 欧拉函数 <= x中与x互素的个数 
int vis[maxn];
int pri[maxn];
int tot = 0;
// 素数筛 求欧拉函数 
/*
素数p的欧拉值 
phi(p) = p - 1;

合数x的欧拉值 
x = p1^k1 * p2^k2 * ... pr^kr. p1,p2,...,pr为素数且p1
void prime_init(int n) {
    phi[1] = 0;
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
        	pri[++tot] = i;
			phi[i] = i - 1;// 素数x的欧拉函数值为x-1 
		}
        for (int j = 1; j <= tot && i * pri[j] <= n; ++j) {
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
            	// 根据欧拉函数的定义 
				// phi(x*p) = phi(x) * p, x % p == 0,p为素数 
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
            // 根据欧拉函数的定义 
			// phi(x*p) = phi(x) * (p-1), gcd(x,p)==1,p为素数 
            phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
    }
}
int lcm(int x, int y) {
	return 1LL * x * y / __gcd(x, y) % mod;
}
void solve() {
	scanf("%d", &n);
	ll res = 0;
	for (int c = 1; c <= n - 2; ++c) {
		int tmp = n - c;
		for (int d = 1; d <= tmp / d; ++d) {
			if (tmp % d != 0) {
				continue;
			}
			res += 1LL * lcm(c, d) * phi[tmp / d] % mod, res %= mod;
			if (d != tmp / d)
				res += 1LL * lcm(c, tmp / d) * phi[d] % mod, res %= mod;
		}
	}
	printf("%lld\n", res);
}

int main() {
	int t;
	prime_init(maxn - 5);
//	scanf("%d", &t);
	t = 1; 
	while (t--) {
		solve();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

最后

觉得文章不错子，WX GZH搜索 对方正在debug，一起快乐刷题吧~