怎么用自己的网站做邮箱,企业建站套餐价格表,成都热点新闻最新,高清视频素材下载网站正题 题目大意 ∑d∣nf(d)n\sum_{d|n}f(d)nd∣n∑f(d)n 对于n个aia_iai 求 ∑i1nf(ai)\sum_{i1}^nf(a_i)i1∑nf(ai) 解题思路——莫比乌斯反演
这个方法对于aia_iai比较大时比较好用#xff0c;但是事实证明本题过不了。 用莫比乌斯反演可得到此公式 f(n)∑d∣nμ(…正题 题目大意
∑d∣nf(d)n\sum_{d|n}f(d)nd∣n∑f(d)n 对于n个aia_iai 求 ∑i1nf(ai)\sum_{i1}^nf(a_i)i1∑nf(ai) 解题思路——莫比乌斯反演
这个方法对于aia_iai比较大时比较好用但是事实证明本题过不了。 用莫比乌斯反演可得到此公式 f(n)∑d∣nμ(d)∗ndf(n)\sum_{d|n}\mu(d)*\frac{n}{d}f(n)d∣n∑μ(d)∗dn 根据莫比乌斯函数的性质可以将n分解质因数然后搜索分解的质因数然后搜索每个质因数选或不选来计算答案 时间复杂度:O(nlogai)O(n\ \ log\ a_i)O(n log ai) code——莫比乌斯反演
\
#includecstdio
#define N 10000010
#define ll long long
using namespace std;
ll ans,n,cnt,p[1000],a;
ll read(){ll x0,flag1;char chgetchar();while(ch0||ch9){if(ch-)flag-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}return x*flag;
}
void write(ll x)
{if(x9) write(x/10);putchar(x%1048);return;
}
void dfs(ll x,ll sum,ll c)//搜索
{if(xcnt){ansa/sum*((c%2)?-1:1);return;}dfs(x1,sum*p[x],c1);dfs(x1,sum,c);
}
void get_ans(ll n)//获取答案
{cnt0;an;for(ll i2;i*in;i){if(n%i0) p[cnt]i;while(n%i0) n/i;}if(n1) p[cnt]n;dfs(1,1,0);
}
int main()
{nread();if(n30000000){get_ans(7);write(ans*30000000);return 0;}ans0;for(ll i1;in;i)get_ans(read());write(ans);
}解题思路——欧拉函数
注:最后几个点要打表 我们其实可以发现f(ai)φ(ai)f(a_i)\varphi(a_i)f(ai)φ(ai) 时间复杂度:O(max{ai}n)O(max\{a_i\}n)O(max{ai}n) code——欧拉函数
#includecstdio
#define ll long long
#define N int(1e7)10
using namespace std;
ll n,a,phi[N],prime[N],ans,m,v[N];
void euler(ll n)//线性
{m0;phi[1]1;for(ll i2;in;i){if(v[i]0){v[i]i,prime[m]i;phi[i]i-1;}for(ll j1;jm;j){if(prime[j]v[i]||prime[j]n/i) break;v[i*prime[j]]prime[j];phi[i*prime[j]]phi[i]*(i%prime[j]?prime[j]-1:prime[j]);}}
}
int main()
{scanf(%lld,n);if (n30000000) return !printf(180000000);else if (n3) return !printf(525162079891401242);else if (n5) return !printf(21517525747423580);euler(N-10);for(ll i1;in;i){scanf(%lld,a);ansphi[a];}printf(%lld,ans);
}
