題目描述

輸入描述:

輸出描述:

示例1
輸入
3
輸出
5

分析：

1.這個題其實考的是一個莫比烏斯反演題，但是由于我知識儲備不夠，沒有看出來，題目給的范圍可以瞎搞一下，所以下面容斥可以過。
2.轉(zhuǎn)換一下就是一道經(jīng)典的反演題，參考

AC代碼：

容斥：

#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; typedef long long ll; const int M=1e5+10; int f[M]; int cal(int x){int num=0;while(x){num+=x%10;x/=10;}return num; } int main(){int n;cin>>n;ll ans=0;for(int i=2;i<=n;i++){int m=i,kk=0;for(int j=2;j*j<=n;j++){///唯一分解定理，求其素因子if(m%j==0){f[kk++]=j;while(m%j==0)m/=j;}}if(m>1) f[kk++]=m;int lim=1<<kk,sum=0;for(int j=1;j<lim;j++){///枚舉哪些質(zhì)因子被拿出來了int x=j,su=0,sm=1;for(int k=0;k<kk;k++){///找出哪些素因子被拿出if(x&(1<<k)){su++;sm*=f[k];}}if(su&1) sum+=n/sm-i/sm;///規(guī)定，當(dāng)素因子拿出奇數(shù)個，則加上，在（i~n）里存在該質(zhì)因子數(shù)的個數(shù)。else sum-=n/sm-i/sm;///當(dāng)為偶數(shù)時，此時之前已經(jīng)拿出，重復(fù)，需減掉。}///sum為不互質(zhì)的數(shù)；///n-i，為總數(shù)，原為找尋的for(j=i+1,j<=n;j++)中(i,j)互質(zhì)的數(shù)ans+=(n-i-sum)*cal(i);}ans+=n;///沒有枚舉1，因為全部會被標(biāo)記，所以+1cout<<ans<<endl;return 0; }

莫比烏斯反演：

#include<stdio.h> #include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int M=1e5+10; int prime[M],mu[M],f[M]; int cnt; bool book[M]; void sieve(int N) {mu[1]=1;for(int i=2; i<=N; i++){if(!book[i])prime[cnt++]=i,mu[i]=-1;for(int j=0; prime[j]<=N/i; j++){book[i*prime[j]]=true;if(i%prime[j]==0)break;mu[i*prime[j]]=-mu[i];}}for(int i = 0; i <= N; i++){int x = i;while(x){f[i]+=x%10;x/=10;}} } int main() {sieve(M - 1);int n;scanf("%d",&n);ll ans=0;for(int i=1; i<=n; i++){if(!mu[i])continue;ll res=0;for(int j=1; j<=n/i; j++)res+=(ll)f[j*i]*(n/i-j+1);//1LL,長整型1，和*1.0一樣，改變數(shù)據(jù)類型用;ans+=mu[i]*res;}printf("%lld\n",ans);return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的莫比乌斯反演/容斥 +2020ICPC 江西省大学生程序设计竞赛 A Simple Math Problem的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。