↵
↵
↵
↵
Translated by Baidu:↵
↵
Analysis:↵
↵
Well, it's said that there's a O (N√N) method. But I didn't think so in the examination room. I'd like to write my O (n) algorithm.↵
↵
↵
↵
First of all, it is obvious that if we can get together, we must satisfy a|A, b|B, c|C (divisor).↵
↵
↵
↵
So, the problem is transformed into the number of solutions satisfying a|A, b|B and c|C in the three tuple (a, b, c) (a <= b <= c).↵
↵
We use the idea of inclusion and exclusion to find out a larger set containing the solution and subtract the duplicate part.↵
↵
↵
↵
We can first ignore the conditions (a <=b <= c), that is, without considering the order, making 1,2,3 and 1,3,2 different schemes.↵
↵
↵
↵
Let f (x) represent the number of factors of X↵
↵
↵
↵
The total number of such schemes is f (A) x f (B) x f (C)↵
↵
Now consider what is repeated. It is not hard to think that if a, b, and c are repeatedly calculated, there must be two elements to satisfy a, b|gcd (A, B).↵
↵
In this way, we can take all the statistics into account.↵
↵
↵
↵
1, a, b|gcd (A, B), c|C↵
↵
In this case, there will be two situations: (a, B, c), (B, a, c). After eliminating a=b, it will be subtracted once, so f (GCD (A, B)) minus (f (GCD (A)) 1 (2) is (f).↵
↵
Similarly, there are cases of B, c|gcd (B, C), a|A, a, c|gcd (A, C), b|B.↵
↵
↵
↵
But there is a problem, which is somewhat reduced, namely, a, B, c|gcd (A, B, C).↵
↵
This is again divided into two cases:↵
↵
↵
↵
a=b≠c:↵
↵
Give a specific example to illustrate:↵
↵
For example (1,2,2)↵
↵
When considering GCD (A, B), we subtract once (1,2,2).↵
↵
When GCD (B, C) is considered, one time (2,1,2) is subtracted↵
↵
When GCD (A, C) is considered, one time (2,2,1) is subtracted↵
↵
The total was subtracted 3 times. However, it was repeated 3 times at the very beginning (C13). So it was reduced.↵
↵
So add it, that is, add f (GCD (A, B, C)) * (f (GCD (A, B, C))-1).↵
↵
The above is divided by 2, but it is not divided by 2, because the above (a, b) and (B, a) is a situation, but here is (a, a, b) and (B, B, a), not a situation.↵
↵
↵
↵
a≠b≠c:↵
↵
Try to explain it with an example.↵
↵
For example, (1,2,3) this group↵
↵
↵
↵
When considering GCD (A, B), we subtract one (1,2,3), (1,3,2), (2,3,1).↵
↵
When considering GCD (B, C), we subtract one (3,1,2), (2,1,3), (1,2,3).↵
↵
When considering GCD (A, C), we subtract one (2,3,1), (3,2,1), (3,1,2).↵
↵
The total was subtracted 9 times, but at the beginning it was repeated 6 times (3!). It should have been subtracted 5 times, but it has been reduced by 4 times, so it has been added 4 times.↵
↵
That is to say, add f (GCD (A, B, C)) * (f (GCD (A, B, C)) -1 ) * (f (GCD (A, B, C)) — 2)/6*4↵
↵
2, a, b|gcd (A, B, C), but c/|C（not divisible）, c|A, c|B↵
↵
It may also be illustrated by an example.↵
↵
For A=4, B=4, C=6↵
↵
When the three tuple is calculated (1,2,4)↵
↵
We first calculated (1,4,2), (2,4,1), (4,1,2), (4,2,1) four times.↵
↵
↵
↵
But when we consider GCD (A, B), we subtract (1,4,2), (2,4,1).↵
↵
When GCD (B, C) is considered, it is subtracted (4,1,2)↵
↵
When GCD (A, C) is considered, it is subtracted (1,4,2)↵
↵
So it was cut 4 times. It's going to be mended once.↵
↵
So add (f (GCD (A, B))-f (GCD (A, B, C))) * f (GCD (A, B, C) *f( (GCD (A, B, C)-1)/2↵
↵
In the same way, there are B, c|gcd (A, B, C), a|A but a/|gcd (A, B, C).↵
↵
And a, c|gcd (A, B, C), b|B but b/|gcd (A, B, C)↵
↵
3, a|gcd (A, B) but a/|C, b|gcd (B, C) but b/|A, c|gcd (A, C) but A.↵
↵
For example, when A=6, B=10, C=15↵
↵
Consider (2,3,5) this group↵
↵
It will be calculated to (3,2,5), (2,5,3) these two times, but we did not decrease at one time.↵
↵
So minus one time, that is, subtract↵
↵
(f (GCD (A, B))-f (GCD (A, B, C))) * (f (GCD (B, C))-f (GCD (A, B, C))) * (f (GCD (A, C))-f (GCD (A, B, C)))↵
↵
At this point, all the circumstances have been considered.↵
↵
``↵
`~~~~~`↵
`#include<cstdio>↵
#include<cstring>↵
#include<cmath>↵
#include<algorithm>↵
#define SF scanf↵
#define PF printf↵
#define MAXN 100010↵
using namespace std;↵
int n;↵
typedef long long ll;↵
ll f[MAXN],num[MAXN];↵
int primes[MAXN],isprime[MAXN],tot;↵
void prepare(){↵
f[1]=1;↵
for(int i=2;i<=100000;i++){↵
if(isprime[i]==0){↵
primes[++tot]=i;↵
f[i]=2;↵
num[i]=1;↵
}↵
for(int j=1;j<=tot&&i*primes[j]<=100000;j++){↵
isprime[i*primes[j]]=1;↵
if(i%primes[j]==0){↵
num[i*primes[j]]=num[i]+1;↵
f[i*primes[j]]=f[i]/(num[i]+1ll)*(num[i*primes[j]]+1ll);↵
break;↵
}↵
f[i*primes[j]]=f[i]*f[primes[j]];↵
num[i*primes[j]]=1;↵
}↵
}↵
}↵
int gcd(int x,int y){↵
if(y==0)↵
return x;↵
return gcd(y,x%y);↵
}↵
int main(){↵
prepare();↵
int t,a,b,c;↵
SF("%d",&t);↵
for(int i=1;i<=t;i++){↵
SF("%d%d%d",&a,&b,&c);↵
//PF("{%lld %lld %lld}\n",f[a],f[b],f[c]);↵
//PF("{%d %d %d}",gcd(a,b),gcd(b,c),gcd(a,c));↵
int ab=gcd(a,b),bc=gcd(b,c),ac=gcd(a,c);↵
ll ans1=f[a]*f[b]*f[c]; ↵
ll ans2=(f[ab]*f[ab]-f[ab])/2ll*f[c];↵
ll ans3=f[a]*(f[bc]*f[bc]-f[bc])/2ll;↵
ll ans4=f[b]*(f[ac]*f[ac]-f[ac])/2ll;↵
int td=gcd(gcd(a,c),b);↵
ll ans5=(f[td]*f[td]-f[td])+f[td]*(f[td]-1ll)*(f[td]-2ll)/6ll*4ll;↵
ll ans6=(f[ab]-f[td])*f[td]*(f[td]-1ll)/2ll;↵
ll ans7=(f[bc]-f[td])*f[td]*(f[td]-1ll)/2ll;↵
ll ans8=(f[ac]-f[td])*f[td]*(f[td]-1ll)/2ll;↵
ll ans9=(f[ab]-f[td])*(f[bc]-f[td])*(f[ac]-f[td]);↵
ll ans=ans1-ans2-ans3-ans4+ans5+ans6+ans7+ans8-ans9;↵
/*if(ans==212)↵
PF("[%d,%d,%d]\n",a,b,c);*/↵
//PF("%lld %lld %lld %lld %lld",ans1,ans2,ans3,ans4,ans5); ↵
PF("%I64d\n",ans);↵
}↵
} `↵
`~~~~~`↵
``↵
````
↵
↵
↵
Translated by Baidu:↵
↵
Analysis:↵
↵
Well, it's said that there's a O (N√N) method. But I didn't think so in the examination room. I'd like to write my O (n) algorithm.↵
↵
↵
↵
First of all, it is obvious that if we can get together, we must satisfy a|A, b|B, c|C (divisor).↵
↵
↵
↵
So, the problem is transformed into the number of solutions satisfying a|A, b|B and c|C in the three tuple (a, b, c) (a <= b <= c).↵
↵
We use the idea of inclusion and exclusion to find out a larger set containing the solution and subtract the duplicate part.↵
↵
↵
↵
We can first ignore the conditions (a <=b <= c), that is, without considering the order, making 1,2,3 and 1,3,2 different schemes.↵
↵
↵
↵
Let f (x) represent the number of factors of X↵
↵
↵
↵
The total number of such schemes is f (A) x f (B) x f (C)↵
↵
Now consider what is repeated. It is not hard to think that if a, b, and c are repeatedly calculated, there must be two elements to satisfy a, b|gcd (A, B).↵
↵
In this way, we can take all the statistics into account.↵
↵
↵
↵
1, a, b|gcd (A, B), c|C↵
↵
In this case, there will be two situations: (a, B, c), (B, a, c). After eliminating a=b, it will be subtracted once, so f (GCD (A, B)) minus (f (GCD (A)) 1 (2) is (f).↵
↵
Similarly, there are cases of B, c|gcd (B, C), a|A, a, c|gcd (A, C), b|B.↵
↵
↵
↵
But there is a problem, which is somewhat reduced, namely, a, B, c|gcd (A, B, C).↵
↵
This is again divided into two cases:↵
↵
↵
↵
a=b≠c:↵
↵
Give a specific example to illustrate:↵
↵
For example (1,2,2)↵
↵
When considering GCD (A, B), we subtract once (1,2,2).↵
↵
When GCD (B, C) is considered, one time (2,1,2) is subtracted↵
↵
When GCD (A, C) is considered, one time (2,2,1) is subtracted↵
↵
The total was subtracted 3 times. However, it was repeated 3 times at the very beginning (C13). So it was reduced.↵
↵
So add it, that is, add f (GCD (A, B, C)) * (f (GCD (A, B, C))-1).↵
↵
The above is divided by 2, but it is not divided by 2, because the above (a, b) and (B, a) is a situation, but here is (a, a, b) and (B, B, a), not a situation.↵
↵
↵
↵
a≠b≠c:↵
↵
Try to explain it with an example.↵
↵
For example, (1,2,3) this group↵
↵
↵
↵
When considering GCD (A, B), we subtract one (1,2,3), (1,3,2), (2,3,1).↵
↵
When considering GCD (B, C), we subtract one (3,1,2), (2,1,3), (1,2,3).↵
↵
When considering GCD (A, C), we subtract one (2,3,1), (3,2,1), (3,1,2).↵
↵
The total was subtracted 9 times, but at the beginning it was repeated 6 times (3!). It should have been subtracted 5 times, but it has been reduced by 4 times, so it has been added 4 times.↵
↵
That is to say, add f (GCD (A, B, C)) * (f (GCD (A, B, C)) -1 ) * (f (GCD (A, B, C)) — 2)/6*4↵
↵
2, a, b|gcd (A, B, C), but c/|C（not divisible）, c|A, c|B↵
↵
It may also be illustrated by an example.↵
↵
For A=4, B=4, C=6↵
↵
When the three tuple is calculated (1,2,4)↵
↵
We first calculated (1,4,2), (2,4,1), (4,1,2), (4,2,1) four times.↵
↵
↵
↵
But when we consider GCD (A, B), we subtract (1,4,2), (2,4,1).↵
↵
When GCD (B, C) is considered, it is subtracted (4,1,2)↵
↵
When GCD (A, C) is considered, it is subtracted (1,4,2)↵
↵
So it was cut 4 times. It's going to be mended once.↵
↵
So add (f (GCD (A, B))-f (GCD (A, B, C))) * f (GCD (A, B, C) *f( (GCD (A, B, C)-1)/2↵
↵
In the same way, there are B, c|gcd (A, B, C), a|A but a/|gcd (A, B, C).↵
↵
And a, c|gcd (A, B, C), b|B but b/|gcd (A, B, C)↵
↵
3, a|gcd (A, B) but a/|C, b|gcd (B, C) but b/|A, c|gcd (A, C) but A.↵
↵
For example, when A=6, B=10, C=15↵
↵
Consider (2,3,5) this group↵
↵
It will be calculated to (3,2,5), (2,5,3) these two times, but we did not decrease at one time.↵
↵
So minus one time, that is, subtract↵
↵
(f (GCD (A, B))-f (GCD (A, B, C))) * (f (GCD (B, C))-f (GCD (A, B, C))) * (f (GCD (A, C))-f (GCD (A, B, C)))↵
↵
At this point, all the circumstances have been considered.↵
↵
``↵
`~~~~~`↵
`#include<cstdio>↵
#include<cstring>↵
#include<cmath>↵
#include<algorithm>↵
#define SF scanf↵
#define PF printf↵
#define MAXN 100010↵
using namespace std;↵
int n;↵
typedef long long ll;↵
ll f[MAXN],num[MAXN];↵
int primes[MAXN],isprime[MAXN],tot;↵
void prepare(){↵
f[1]=1;↵
for(int i=2;i<=100000;i++){↵
if(isprime[i]==0){↵
primes[++tot]=i;↵
f[i]=2;↵
num[i]=1;↵
}↵
for(int j=1;j<=tot&&i*primes[j]<=100000;j++){↵
isprime[i*primes[j]]=1;↵
if(i%primes[j]==0){↵
num[i*primes[j]]=num[i]+1;↵
f[i*primes[j]]=f[i]/(num[i]+1ll)*(num[i*primes[j]]+1ll);↵
break;↵
}↵
f[i*primes[j]]=f[i]*f[primes[j]];↵
num[i*primes[j]]=1;↵
}↵
}↵
}↵
int gcd(int x,int y){↵
if(y==0)↵
return x;↵
return gcd(y,x%y);↵
}↵
int main(){↵
prepare();↵
int t,a,b,c;↵
SF("%d",&t);↵
for(int i=1;i<=t;i++){↵
SF("%d%d%d",&a,&b,&c);↵
//PF("{%lld %lld %lld}\n",f[a],f[b],f[c]);↵
//PF("{%d %d %d}",gcd(a,b),gcd(b,c),gcd(a,c));↵
int ab=gcd(a,b),bc=gcd(b,c),ac=gcd(a,c);↵
ll ans1=f[a]*f[b]*f[c]; ↵
ll ans2=(f[ab]*f[ab]-f[ab])/2ll*f[c];↵
ll ans3=f[a]*(f[bc]*f[bc]-f[bc])/2ll;↵
ll ans4=f[b]*(f[ac]*f[ac]-f[ac])/2ll;↵
int td=gcd(gcd(a,c),b);↵
ll ans5=(f[td]*f[td]-f[td])+f[td]*(f[td]-1ll)*(f[td]-2ll)/6ll*4ll;↵
ll ans6=(f[ab]-f[td])*f[td]*(f[td]-1ll)/2ll;↵
ll ans7=(f[bc]-f[td])*f[td]*(f[td]-1ll)/2ll;↵
ll ans8=(f[ac]-f[td])*f[td]*(f[td]-1ll)/2ll;↵
ll ans9=(f[ab]-f[td])*(f[bc]-f[td])*(f[ac]-f[td]);↵
ll ans=ans1-ans2-ans3-ans4+ans5+ans6+ans7+ans8-ans9;↵
/*if(ans==212)↵
PF("[%d,%d,%d]\n",a,b,c);*/↵
//PF("%lld %lld %lld %lld %lld",ans1,ans2,ans3,ans4,ans5); ↵
PF("%I64d\n",ans);↵
}↵
} `↵
`~~~~~`↵
``↵
````
