站长查询域名,海港开发区人才网,网站 扁平化,图片代码如何做网站正题
P2568 题目大意
求满足1≤x,y≤n1\leq x,y\leq n1≤x,y≤n且gcd(x,y)primegcd(x,y)primegcd(x,y)prime的数对(x,y)(x,y)(x,y)的个数 解题思路
题目即求 ∑i1n∑j1n[gcd(i,j)prime]\sum_{i1}^n\sum_{j1}^n[gcd(i,j)prime]i1∑nj1∑n[gcd(i,j)prime]
可以考虑先枚举…正题
P2568 题目大意
求满足1≤x,y≤n1\leq x,y\leq n1≤x,y≤n且gcd(x,y)primegcd(x,y)primegcd(x,y)prime的数对(x,y)(x,y)(x,y)的个数 解题思路
题目即求
∑i1n∑j1n[gcd(i,j)prime]\sum_{i1}^n\sum_{j1}^n[gcd(i,j)prime]i1∑nj1∑n[gcd(i,j)prime]
可以考虑先枚举该prime那么有
∑p∈primen∑i1n/p∑j1n/p[gcd(i,j)1]∑p∈primen∑i1n/p∑j1n/p∑d∣i,d∣jμ(d)∑p∈primen∑d1n/pμ(d)×⌊nd⌋×⌊nd⌋\sum_{p\in prime}^n\sum_{i1}^{n/p}\sum_{j1}^{n/p}[gcd(i,j)1]\\ \sum_{p\in prime}^n\sum_{i1}^{n/p}\sum_{j1}^{n/p}\sum_{d|i,d|j}\mu(d)\\ \sum_{p\in prime}^n\sum_{d1}^{n/p}\mu(d)\times \left\lfloor\frac{n}{d}\right\rfloor\times \left\lfloor\frac{n}{d}\right\rfloor p∈prime∑ni1∑n/pj1∑n/p[gcd(i,j)1]p∈prime∑ni1∑n/pj1∑n/pd∣i,d∣j∑μ(d)p∈prime∑nd1∑n/pμ(d)×⌊dn⌋×⌊dn⌋
时间复杂度不太会证看dalao证的是 O(n/logn)O(n/log n)O(n/logn)的 code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 10000010
using namespace std;
ll n,ans,w,p[N],mu[N],prime[N];
void work()
{p[1]mu[1]1;for(ll i2;i10000000;i){if(!p[i]){prime[w]i;mu[i]-1;}for(ll j1;jwi*prime[j]10000000;j){p[i*prime[j]]1;if(i%prime[j]0){mu[i*prime[j]]0;break;}else mu[i*prime[j]]-mu[i];}}for(ll i2;i10000000;i)mu[i]mu[i-1];return;
}
ll get(ll n)
{ll sum0;for(ll l1,r0;ln;lr1){rn/(n/l);sum(mu[r]-mu[l-1])*(n/l)*(n/l);}return sum;
}
int main()
{scanf(%lld,n);work();for(ll i1;iw;i)if(prime[i]n)ansget(n/prime[i]);else break;printf(%lld,ans);return 0;
}
