最大公约数
2021/7/21 23:06:50
本文主要是介绍最大公约数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
最大公约数
思路 :
\(gcd(x,y)=p,1\le x,y \le n \Rightarrow gcd(\frac{x}{p},\frac{y}{p})=1 \Rightarrow gcd(x′,y′)=1,1 \le x′,y′\le \frac{n}{p}\)
所以其实很经典的在矩形(n*n)坐标范围下求 \((x,y)\) 的互质对数.只不过这里的 \(n\) 也是变量.
本题扩展于可见的点
#include <bits/stdc++.h> using namespace std; #define IO ios::sync_with_stdio(false);cin.tie(0); cout.tie(0); inline int lowbit(int x) { return x & (-x); } #define ll long long #define ull unsigned long long #define pb push_back #define PII pair<int, int> #define VIT vector<int> #define x first #define y second #define inf 0x3f3f3f3f const int N = 1e7 + 10; int pri[N], cnt; bool st[N]; ll phi[N]; void init() { phi[1] = 1; for (int i = 2; i < N; ++i) { if (!st[i]) { pri[cnt++] = i; phi[i] = i - 1; } for (int j = 0; pri[j] * i < N; ++j) { st[pri[j] * i] = true; if (i % pri[j] == 0) { phi[pri[j] * i] = phi[i] * pri[j]; break; } phi[pri[j] * i] = phi[i] * (pri[j] - 1); } } } int main() { IO; init(); int n; cin >> n; phi[1] = 0; for (int i = 2; i < N; ++i) phi[i] += phi[i - 1]; ll ans = 0; for (int i = 0; pri[i] <= n; ++i) ans += phi[n / pri[i]] * 2 + 1; cout << ans << '\n'; return 0; }
这篇关于最大公约数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-26JavaScript入门教程:从零开始学习JavaScript编程
- 2024-12-26JavaScript入门教程:从零开始学习JavaScript
- 2024-12-26JS编程入门指南:从零开始学习JavaScript
- 2024-12-25Java编程面试题详解与解答
- 2024-12-25TS基础知识详解:初学者必看教程
- 2024-12-252024面试题解析与攻略:从零开始的面试准备指南
- 2024-12-25数据结构与算法学习:新手入门教程
- 2024-12-25初学者必备:订单系统资料详解与实操教程
- 2024-12-24内网穿透资料入门教程
- 2024-12-24微服务资料入门指南