首页 > 代码库 > BZOJ 1040 最大公约数之和
BZOJ 1040 最大公约数之和
Description
求\(\sum_{i=1}^n(i,n),n\leqslant 10^9\)
Solution
\(\sum_{i=1}^n(i,n)=\sum_{d\mid n}d\sum_{i=1}^n[(i,n)=d]=\sum_{d\mid n}\sum_{i=1}^{\frac{n}{d}}[(i,\frac{n}{d})=1]=\sum_{d\mid n}\varphi(\frac{n}{d})\)
复杂度好像和杜教筛挺像的?口胡+1...我不太会算...
Code
#include <bits/stdc++.h>using namespace std;typedef long long ll;ll phi(ll x) { ll r=x; for(int i=2;i*i<=x && x>1;i++) if(x%i==0) { r=r/i*(i-1),x/=i; for(;x%i==0;x/=i); }if(x>1) r=r/x*(x-1);return r;}ll S(ll n) { return n*(n+1)/2; }ll S(ll l,ll r) { return S(r)-S(l-1); }ll F(ll n) { ll r=0; for(int i=1;i*i<=n;i++) if(n%i==0) { r=r+i*phi(n/i); if(i*i==n) continue; r=r+n/i*phi(i); }return r;}int main() { ll n; scanf("%lld",&n); printf("%lld\n",F(n)); return 0;}
BZOJ 1040 最大公约数之和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。