1 /** 2 大意: 求解 在[1，n] x， [1，m] y，之间有多少个gcd（x，y） = d d = min（n，m） 3 思路： 对于任意一个d 在[1，n] x， [1，m] y， gcd（x，y） 含有d 因子的个数为 n/i * m/i 这是所有含有因子d的组合的个数 ， 再减去 gcd（x，y） = 2*d ， gcd（x，y） = 3*d， gcd（x，y） = 4*d。。。那么最后得到的就是最大公约数为d的组合的个数 4 5 siga( 1-n ) * siga(1-m) 2* (gcd(x,y)-1) + 1 ===>siga( 1-n(x) ) * siga(1-m(y)) 2* (gcd(x,y)-1) + n*m 6 **/ 7 #include <iostream> 8 #include <algorithm> 9 #include <cstring> 10 using namespace std; 11 12 long long cnt[100050]; 13 14 int main() 15 { 16 long long n,m; 17 while(cin>>n>>m){ 18 memset(cnt,0,sizeof(cnt)); 19 int t = min(n,m); 20 for(int i=2;i<=t;i++) 21 cnt[i] = (n/i)*(m/i); 22 for(int i=t;i>=1;i--){ 23 for(int k=2;k*i<=t;k++) 24 cnt[i] -= cnt[i*k]; 25 } 26 long long ans =0; 27 for(int i=1;i<=t;i++) 28 ans += 2*(i-1)*cnt[i]; 29 ans += n*m; 30 cout<<ans<<endl; 31 } 32 return 0; 33 }