百度推广培训机构,爱网站推广优化,网站型营销,广东 网站经营性备案题目描述 输入描述:
输出描述: 示例1 输入 3 输出 5
分析#xff1a;
1.这个题其实考的是一个莫比乌斯反演题#xff0c;但是由于我知识储备不够#xff0c;没有看出来#xff0c;题目给的范围可以瞎搞一下#xff0c;所以下面容斥可以过。 2.转换一下就是一道经典的…题目描述 输入描述:
输出描述: 示例1 输入 3 输出 5
分析
1.这个题其实考的是一个莫比乌斯反演题但是由于我知识储备不够没有看出来题目给的范围可以瞎搞一下所以下面容斥可以过。 2.转换一下就是一道经典的反演题参考
AC代码
容斥
#includestdio.h
#includestring.h
#includealgorithm
#includeiostream
using namespace std;
typedef long long ll;
const int M1e510;
int f[M];
int cal(int x){int num0;while(x){numx%10;x/10;}return num;
}
int main(){int n;cinn;ll ans0;for(int i2;in;i){int mi,kk0;for(int j2;j*jn;j){///唯一分解定理求其素因子if(m%j0){f[kk]j;while(m%j0)m/j;}}if(m1) f[kk]m;int lim1kk,sum0;for(int j1;jlim;j){///枚举哪些质因子被拿出来了int xj,su0,sm1;for(int k0;kkk;k){///找出哪些素因子被拿出if(x(1k)){su;sm*f[k];}}if(su1) sumn/sm-i/sm;///规定当素因子拿出奇数个则加上在i~n里存在该质因子数的个数。else sum-n/sm-i/sm;///当为偶数时此时之前已经拿出重复需减掉。}///sum为不互质的数///n-i为总数原为找寻的for(ji1,jn;j)中(i,j)互质的数ans(n-i-sum)*cal(i);}ansn;///没有枚举1因为全部会被标记所以1coutansendl;return 0;
}莫比乌斯反演
#includestdio.h
#includeiostream
#includecstring
#includealgorithm
using namespace std;
typedef long long ll;
const int M1e510;
int prime[M],mu[M],f[M];
int cnt;
bool book[M];
void sieve(int N)
{mu[1]1;for(int i2; iN; i){if(!book[i])prime[cnt]i,mu[i]-1;for(int j0; 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 ans0;for(int i1; in; i){if(!mu[i])continue;ll res0;for(int j1; jn/i; j)res(ll)f[j*i]*(n/i-j1);//1LL,长整型1和*1.0一样改变数据类型用;ansmu[i]*res;}printf(%lld\n,ans);return 0;
}
