反演裸题，乱搞就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool pd[200005];
ll p[200005],mu[200005],s[200005];
ll f[200005];
void getmu(int n){
    ll ps=0; mu[1]=1;
    for (ll i=2;i<=n;i++){
        if (pd[i]==0) mu[i]=-1,ps++,p[ps]=i;
        for (ll j=1;j<=ps;j++){
            if (i*p[j]>n) break;
            pd[i*p[j]]=1;
            if (i%p[j]==0){
                mu[i*p[j]]=0; break;
            }
            mu[i*p[j]]=-mu[i];
        }
    }
    s[0]=0;
    for (ll i=1;i<=n;i++)
    s[i]=mu[i]+s[i-1];
}
ll fy(int n,int m,int d){
    ll ans=0;
    n/=d; m/=d;
    for (int i=1;i<=n;i){
        int las=min(n/(n/i),m/(m/i));
        ans+=(s[las]-s[i-1])*(n/i)*(m/i);
        i=las+1;
    }
    return ans;
}
int main(){
    int n,m; 
    scanf("%d%d",&n,&m);
    if (n>m) swap(n,m);
    memset(pd,0,sizeof(pd));
    getmu(m);
    for (int i=1;i<=n;i++){
        f[i]=fy(n,m,i);
    }
    ll ans=0;
    for (int i=1;i<=n;i++){
        ans+=2*(i-1)*f[i]+f[i];
    }
    printf("%lld\n",ans);
    return 0;
} 

题解

注意计算出来的中间结果的类型，否则最后一个测试点会溢出。

#include <stdio.h>

long long f[100001];
long long n, m;

int main()
{
    long long mx;
    int i, j;
    long long ans = 0;
    scanf("%lld%lld", &n, &m);
    if (n > m) mx = m;
    else mx = n;
    for (i = mx; i >= 1; i--) {
        f[i] = (n / i) * (m / i);
        for (j = i * 2; j <= mx; j += i) {
            f[i] -= f[j];
        }
    }
    for (i = 1; i <= mx; i++) {
        ans += f[i] * (2 * i - 1);
    }
    printf("%lld", ans);
    return 0;
}

http://www.cnblogs.com/JSZX11556/p/4676872.html 容斥

测试数据 #0: Accepted, time = 15 ms, mem = 1296 KiB, score = 10

测试数据 #1: Accepted, time = 15 ms, mem = 1292 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 1292 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 1296 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 1292 KiB, score = 10

测试数据 #5: Accepted, time = 1 ms, mem = 1292 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 1292 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 1296 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 1296 KiB, score = 10

测试数据 #9: Accepted, time = 18 ms, mem = 1292 KiB, score = 10

Accepted, time = 79 ms, mem = 1296 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>

using namespace std;

inline long long min( long long a , long long b )
{
if( a > b )
return b;
return a;
}

long long f[100000 + 2];
long long n , m;
long long ans;
long long i , j;

int main()
{
scanf( "%d %d" , &n , &m );
for( i = min( n , m ) ; i >= 1 ; i-- )
{
f[i] = ( n / i ) * ( m / i );
for( j = 2 * i ; j <= min( n , m ) ; j += i )
f[i] -= f[j];
}
for( i = min( n , m ) ; i >= 1 ; i-- )
ans += f[i] * ( 2 * i - 1 );
cout << ans << endl;
return 0;
}
水题

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std ;

#define ll long long
#define Sum( l , r ) ( sum[ r ] - sum[ l - 1 ] )
#define maxn 100100

bool f[ maxn ] ;
int u[ maxn ] , n , m , sum[ maxn ] ;
ll ans = 0 ;

void Init( ) {
memset( f , true , sizeof( f ) ) ;
f[ 0 ] = f[ 1 ] = false , u[ 1 ] = 1 ;
for ( int i = 1 ; i ++ < min( n , m ) ; ) if ( f[ i ] ) {
u[ i ] = - 1 ;
for ( int j = i << 1 ; j <= min( n , m ) ; j += i ) {
f[ j ] = false ;
if ( ! ( ( j / i ) % i ) ) u[ j ] = 0 ; else u[ j ] = u[ j / i ] * - 1 ;
}
}
sum[ 0 ] = 0 ;
for ( int i = 0 ; i ++ < min( n , m ) ; ) sum[ i ] = sum[ i - 1 ] + u[ i ] ;
}

ll query( int a , int b ) {
ll ret = 0 ;
for ( int i = 1 ; i <= min( a , b ) ; ) {
int pos = min( a / ( a / i ) , b / ( b / i ) ) ;
ret += ( ll )( Sum( i , pos ) ) * ( ll )( a / i ) * ( ll )( b / i ) ;
i = pos + 1 ;
}
return ret ;
}

int main( ) {
scanf( "%d%d" , &n , &m ) ;
Init( ) ;
for ( int i = 0 ; i ++ < min( n , m ) ; ) {
ans += ( ll )( i ) * query( n / i , m / i ) * 2 ;
}
ans -= ( ll )( n ) * ( ll )( m ) ;
printf( "%lld\n" , ans ) ;
return 0 ;
}

80分很开心了~~~~~~
直接二维n,m然后gcd（n,m),此次能量损失为sqr(gcd(n,m)),并且把斜率记入（相当于已经算了这条线上所有的损失了）

最简单朴素竟然能得80分！