NYOJ 1066 CO-PRIME（数论）
生活随笔
收集整理的這篇文章主要介紹了
NYOJ 1066 CO-PRIME（数论）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
CO-PRIME
時間限制：1000?ms ?|? 內存限制：65535?KB 難度：3 描述This problem is so easy! Can you solve it?
You are given a sequence which contains n integers a1,a2……an, your task is to find how many pair(ai, aj)(i < j) that ai and aj is co-prime.
?
輸入Each test case conatains two line,the first line contains a single integer n,the second line contains n integers.
All the integer is not greater than 10^5.
題意：給出n個正整數，求這n個數中有多少對互素的數。
分析：莫比烏斯反演。
此題中，設F(d)表示n個數中gcd為d的倍數的數有多少對，f(d)表示n個數中gcd恰好為d的數有多少對，
則F(d)=∑f(n)?(n?%?d?==?0)
??f(d)=∑mu[n?/?d]?*?F(n)?(n?%d?==?0)
上面兩個式子是莫比烏斯反演中的式子。
所以要求互素的數有多少對，就是求f(1)。
而根據上面的式子可以得出f(1)=∑mu[n]?*?F(n)。
所以把mu[]求出來，枚舉n就行了，其中mu[i]為i的莫比烏斯函數。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int MAXN = 1e5 + 10; typedef long long LL; int cnt[MAXN], pri[MAXN], num[MAXN], pri_num, mu[MAXN], vis[MAXN], a[MAXN];void mobius(int n) //篩法求莫比烏斯函數 {pri_num = 0;memset(vis, 0, sizeof(vis));vis[1] = mu[1] = 1;for(int i = 2; i <= n; i++) {if(!vis[i]) {pri[pri_num++] = i;mu[i] = -1;}for(int j = 0; j < pri_num; j++) {if(i * pri[j] > n) break;vis[i*pri[j]] = 1;if(i % pri[j] == 0) {mu[i*pri[j]] = 0;break;}mu[i*pri[j]] = -mu[i];}} }LL get(int x) {return (LL)x * (x-1) / 2; }int main() {mobius(100005);int n;while(~scanf("%d",&n)) {int mmax = 0;for(int i = 1; i <= n; i++) {scanf("%d",&a[i]);mmax = max(mmax, a[i]);}memset(cnt, 0, sizeof(cnt));memset(num, 0, sizeof(num));for(int i = 1; i <= n; i++) num[a[i]]++;for(int i = 1; i <= mmax; i++)for(int j = i; j <= mmax; j += i)cnt[i] += num[j];LL ans = 0;for(int i = 1; i <= mmax; i++)ans += get(cnt[i]) * mu[i];printf("%lld\n", ans);}return 0; }
總結
以上是生活随笔為你收集整理的NYOJ 1066 CO-PRIME（数论）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： hdu 1166 敌兵布阵（线段树之 单
- 下一篇： 7月份Github上最热门的Java开源