思路： 化简后得到(a+b)c=ab，设g=(a,b)，A=a/g，B=b/g，则g(A+B)c=ABg^2，即(A+B)c=ABg 由题目已知条件：(a,b,c)=1，即(g,c)=1，g|(A+B)c，故g|(A+B)， 设(A+B)/g=AB/c= k ∈ Z， 若k>1，因为A,B互质，所以k|A或k|B，则A+B不能被k整除，矛盾。因此k=1。 故充要条件为：1<=a,b,c<=n，a+b=g^2，c=ab/g^2。 枚举g，则可得A+B=g。用莫比乌斯反演求出一定范围内与g互质的数的个数即可。 写程序的过程中，你会发现，枚举1到sqrt(2n)的g之后，只需枚举g的约数。 所以时间复杂O(sqrt(n)log(sqrt(n)))
题干:
题目描述 PJY某次翻阅杂志时，看到一道题： 求出所有的正整数三元组{a,b,c}，满足a,b,c<=n，a,b,c三个数的最大公约数为1，且1/a+1/b=1/c。 PJY嫌这道题太水，于是把它甩给了爱数数的LJJ，并加上了数据范围n<=1e12，让LJJ数出有多少组满足条件的三元组{a,b,c} （注意当a不等于b时，{a,b,c}和{b,a,c}是不同的三元组，要算两次） LJJ数到一半，发现这个数量太大了，于是他把问题抛给了你。请你输出这个数量。 输入输出格式 输入格式： 输入仅一行：一个正整数n（n<=1e12） 输出格式： 输出仅一行：一个整数，表示满足条件的三元组{a,b,c}的数量
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; template <class T> void read(T &x) { char c; int op = 0; while(c = getchar(),c > '9' || c < '0') if(c == '-') op = 1; x = c - '0'; while(c = getchar(),c <= '9' && c >= '0') x = x * 10 + c - '0'; if(op) x = -x; } #define duke(i,a,n) for(register int i = a;i <= n;++i) #define lv(i,a,n) for(register int i = a;i >= n;--i) typedef long long ll; typedef double db; #define N 1500000 struct node { int l,r,nxt; }a[20000010]; ll n,ans; int len = 0,lst[N + 1]; bool che[N + 1]; int pri[N + 1],tot = 0,miu[N + 1]; inline void add(int x,int y) { a[++len].l = x; a[len].r = y; a[len].nxt = lst[x]; lst[x] = len; } inline void init() { miu[1] = 1; duke(i,2,N) { if(!che[i]) { pri[++tot] = i; miu[i] = -1; } duke(j,1,tot) { if(i * pri[j] > N) break; che[i * pri[j]] = 1; if(!(i % pri[j])) break; else miu[pri[j] * i] = -miu[i]; } } } inline int getans(int x,int y) { if(y <= 0) return 0; int res = 0; for(int k = lst[x];k;k = a[k].nxt) { if(a[k].r <= y) res += miu[a[k].r] * (y / a[k].r); } return res; } inline ll imax(ll x,ll y) { return x > y ? x : y; } inline ll imin(ll x,ll y) { return x < y ? x : y; } int main() { init(); for(register int i = 1;i <= N;i++) { if(miu[i]) { for(register int j = i;j <= N;j += i) add(j,i); } } //cout<<tot<<endl; read(n);ans = 0; for(register int i = 1;1ll * i * i <= (n * 2);i++) { int low = (imax(1ll,1ll * i * i - n) - 1) / i; int high = (imin(1ll * i * i - 1,n) / i); ans += (ll)getans(i,high) - (ll)getans(i,low); //cout<<ans<<endl; } printf("%lld ",ans); return 0; }