1 #include
     
       2 #include
      
        3 #define ll long long 4 using namespace std; 5 ll f[100009],n,m,ans; 6 int main() 7 { 8     scanf("%d%d",&n,&m); 9     if(n>m)10       swap(n,m);11     for(int i=n;i;i--)12       {13         f[i]=(n/i)*(m/i);14         for(int j=2;j*i<=n;j++)15           f[i]-=f[i*j];16         ans+=f[i]*(2*i-1);17       }18     printf("%lld\n",ans);19     return 0;20 }
      
     

有个结论，(x,y)线段上的端点个数等于gcd(x，y)，证明就自己yy一下吧，然后这个题就变成了gcd的和，设f[i]为gcd为i的点对有多少个，可用程序中方法nlogn求出。