HDU 2588 GCD(欧拉函数)_综合

GCD

思路

题目要求，对于给定的 $n, m$ 要求有多少数 $\sum _{i = 1} ^{n} gcd(i, n) >= m$

我们可以对这个式子进行化简，通过枚举 $d = gcd(i, n)$ 有

$\sum _{d \mid n} \sum _{i = 1} ^{n} gcd(i, d) == d$

$= \sum_{d \mid n} \sum _{i = 1}^{\frac{n}{d}} gcd(i, d) == 1$

$= \sum _{d\mid n} \phi(\frac{n}{d})$

我们只要在统计答案的时候特判一下 $d$ 就行了。

代码

/*Author : lifehappy */
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>#define mp make_pair
#define pb push_back
#define endl '\n'using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;const double pi = acos(-1.0);
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;int eular(int x) {int ans = x;for(int i = 2; i * i <= x; i++) {if(x % i == 0) {while(x % i == 0) {x /= i;}ans = ans / i * (i - 1);}}if(x != 1) ans = ans / x * (x - 1);return ans;
}int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int T, t = 1; cin >> T;while(T--) {int n, m, ans = 0;cin >> n >> m;for(int i = 1; i * i <= n; i++) {if(n % i == 0) {if(i >= m) {ans += eular(n / i);}if(i * i != n && n / i >= m) {ans += eular(i);}}}cout << ans << endl;}return 0;
}