Code(容斥,好题)

Code

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 597    Accepted Submission(s): 230

Problem Description
WLD likes playing with codes.One day he is writing a function.Howerver,his computer breaks down because the function is too powerful.He is very sad.Can you help him?
The function:
int calc {      int res=0;      for(int i=1;i<=n;i++)          for(int j=1;j<=n;j++)          {              res+=gcd(a[i],a[j])*(gcd(a[i],a[j])-1);              res%=10007;          }      return res;
}
 
Input
There are Multiple Cases.(At MOST 10)
For each case:
The first line contains an integer N(1≤N≤10000).
The next line contains N integers a1,a2,...,aN(1≤ai≤10000).
 
Output
For each case:
Print an integer,denoting what the function returns.
 
Sample Input
5
1 3 4 2 4
 
Sample Output
64
Hint

gcd(x,y) means the greatest common divisor of x and y.

题意:就是给你一系列数,让找两个数最大公约数x,求所有x(x-1)的和;其实就是一个容斥,对于每给的一个数,找里面因子出现的次数;

现在我们的任务就是给你一个x为gcd,找以x为gcd出现的次数,最多有count[x]^2次,需要减去多考虑的也就是 2x, 3x, 4x...出现的次数;

f[i]代表以i为gcd出现的次数;

/**********/

首先的思路是,考虑每个数对最终答案的贡献。

那么我们就要求出:对于每个数,以它为 gcd 的数对有多少对。网址:yii666.com

显然,对于一个数 x ,以它为 gcd 的两个数一定都是 x 的倍数。如果 x 的倍数在数列中有 k 个,那么最多有 k^2 对数的 gcd 是 x 。

同样显然的是,对于两个数,如果他们都是 x 的倍数,那么他们的 gcd 一定也是 x 的倍数。网址:yii666.com<文章来源地址:https://www.yii666.com/article/754341.html

所以,我们求出 x 的倍数在数列中有 k 个,然后就有 k^2 对数满足两个数都是 x 的倍数,这 k^2 对数的 gcd,要么是 x ,要么是 2x, 3x, 4x...

并且,一个数是 x 的倍数的倍数,它就一定是 x 的倍数。所以以 x 的倍数为 gcd 的数对,一定都包含在这 k^2 对数中。

如果我们从大到小枚举 x ,这样计算 x 的贡献时,x 的多倍数就已经计算完了。我们用 f(x) 表示以 x 为 gcd 的数对个数。

那么 f(x) = k^2 - f(2x) - f(3x) - f(4x) ... f(tx)             (tx <= 10000, k = Cnt[x])文章来源地址https://www.yii666.com/article/754341.html

这样枚举每个 x ,然后枚举每个 x 的倍数,复杂度是用调和级数计算的,约为 O(n logn)。

/*********/

代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int INF=0x3f3f3f3f;
#define mem(x,y) memset(x,y,sizeof(x))
typedef long long LL;
const int MAXN=10010;
const int MOD=10007;
int cnt[MAXN],f[MAXN];
int main(){
int N;
while(~scanf("%d",&N)){
int x;
mem(cnt,0);mem(f,0);
for(int j=0;j<N;j++){
scanf("%d",&x);
for(int i=1;i<=(int)sqrt(x);i++){
if(x%i==0){
cnt[i]++;
if(x/i!=i)cnt[x/i]++;
}
}
}
int ans=0,temp=0;
for(int i=10000;i>=1;i--){
f[i]=cnt[i]*cnt[i]%MOD;
for(int j=i*2;j<=10000;j+=i)
f[i]=(f[i]-f[j]+MOD)%MOD;
temp=i*(i-1)%MOD;
ans=(ans+f[i]*temp%MOD+MOD)%MOD;
}
printf("%d\n",ans);
}
return 0;
}

  文章地址https://www.yii666.com/article/754341.html

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png