2020ICPC 江西省大学生程序设计竞赛 A Simple Math Problem

本文主要是介绍2020ICPC 江西省大学生程序设计竞赛 A Simple Math Problem，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目:

题目链接:

题解:
莫比乌斯反演

推导过程如下

${\sum }_{i=1}^n{\sum }_{j=1}^{i}F[j][gcd(i,j)=1]$

可以转化为 ${\sum }_{i=1}^{n}F[i]{\sum }_{j=i}^{n}gcd[(i,j)=1]$

${\sum }_{i=1}^{n}F[i]{\sum }_{j=i}^{n}gcd[(i,j)=1]$

= ${\sum }_{i=1}^{n}F[i]{\sum }_{j=i}^n{\sum }_{d|gcd(i,j)}\mu (d)$

= ${\sum }_{d=1}^n\mu (d){\sum }_{i=1}^{[n/d]}F[i\ast d]{\sum }_{j=i}^{[n/d]}1$

=${\sum }_{d=1}^n\mu (d){\sum }_{i=1}^{[n/d]}F[i\ast d](n/i-i+1)$

推导完成

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int st[N],primes[N],mu[N],con,g[N];
void getmus()
{mu[1]=1;for(int i=2;i<=N;i++){if(!st[i]){primes[++con]=i;mu[i]=-1;}for(int j=1;primes[j]*i<=N;j++){int t=primes[j]*i;st[t]=1;if(i%primes[j]==0){break;}mu[t]=-mu[i];}}for(int i=1;i<=N;i++){int n=i;int con=0;while(n){int d=n%10;con+=d;n/=10;}g[i]=con;}
}
int main()
{getmus();int n;cin>>n;long long ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=n/i;j++){ans+=mu[i]*g[j*i]*(n/i-j+1);}}cout<<ans<<endl;return 0;
} 

这篇关于2020ICPC 江西省大学生程序设计竞赛 A Simple Math Problem的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---