首页 > 代码库 > luoguP2398 GCD SUM [gcd]
luoguP2398 GCD SUM [gcd]
题目描述
for i=1 to n
for j=1 to n
sum+=gcd(i,j)给出n求sum. gcd(x,y)表示x,y的最大公约数.
输入输出格式
输入格式：
n
输出格式：
sum
输入输出样例
输入样例#1：
2
输出样例#1：
5
说明
数据范围
30% n<=3000
60% 7000<=n<=7100
100% n<=100000
题目的意思大概是这样的
O(n2)枚举当然是不行的啦。
考虑枚举k，求gcd为k的“数对”的个数。
而可以证明gcd为k的“数对”的个数为
利用容斥把gcd为2k,3k,4k的“数对”的个数减去就好啦？
注意k要从大到小枚举。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 6 typedef long long ll; 7 8 const int maxn=100005; 9 10 int n;11 ll dp[maxn],ans=0;12 13 int main(){14 scanf("%d",&n);15 for(int i=n;i>0;i--){16 dp[i]=1ll*(n/i)*(n/i);17 for(int j=(i<<1);j<=n;j+=i)18 dp[i]-=dp[j];19 ans+=dp[i]*i;20 }21 printf("%lld\n",ans);22 return 0;23 }
luoguP2398 GCD SUM [gcd]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。