网站首页
编程语言
数据库
系统相关
其他分享
编程问答
sumgcd1
2024-07-11
P2568 GCD
原题链接题解令\(g=gcd(i,j)\)则\(i=t_1i,j=t_2j\)所以原题等价于求\(\sum_{i\inprime}\sumgcd(x,y)==1,x\in[1,n/i],y\in[1,n/i]\)也就是对于每个素数\(i\),求\([1,n/i]\)内有几个数互质,我们可以求欧拉函数前缀和得出code#include<bits/stdc++.h>#definelllong