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的最大公约数.

输入输出格式

输入格式：

输出格式：

sum

输入输出样例

输入样例#1：

输出样例#1：

说明

数据范围

30% n<=3000

60% 7000<=n<=7100

100% n<=100000

题目的意思大概是这样的

O(n2)枚举当然是不行的啦。

考虑枚举k，求gcd为k的“数对”的个数。

而可以证明gcd为k的“数对”的个数为

利用容斥把gcd为2k,3k,4k的“数对”的个数减去就好啦？

注意k要从大到小枚举。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 using namespace std;

 typedef long long ll;

 const int maxn=;

 int n;

 ll dp[maxn],ans=;

 int main(){

     scanf("%d",&n);

     for(int i=n;i>;i--){

         dp[i]=1ll*(n/i)*(n/i);

         for(int j=(i<<);j<=n;j+=i)

             dp[i]-=dp[j];

         ans+=dp[i]*i;

     }

     printf("%lld\n",ans);

     return ;

 }

巴特西

luoguP2398 GCD SUM [gcd]

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章