ztx's Blog

/****************************************\
* Author : ztx
* Title  : [Noi2010]能量采集
* ALG    :
* CMT    :
* 位于 (x,y) 的点产生的分值是 gcd(x,y) , 问题转换为求 gcd(x,y) , 答案为 Σ(gcd(x,y)*2-1)
* 考虑 gcd(x,y)=D , D<=10^5 范围不是很大 , 那么我们倒过来考虑 , 我们求解满足 gcd(x,y)=d 的 (x,y) 的个数.
* 有 Σ(gcd(x,y)*2-1) = Σ(F[d]*(d*2-1)) ;
* 其中 F[d] 表示满足 gcd(x,y)=d 的 (x,y) 的个数.
* 考虑以d为公约数的(x,y)的个数g[d]，显然有g[d]=[n/d]*[m/d] ;
* 根据容斥原理有：
* f[d]=g[d]-Σ(f[d*i])  (2<=i<=[min(n,m)/d]) ;
* 这样我们只需要倒过来从min(n,m)反推到1求解即可.
* 时间复杂度O(nlogn)
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [Noi2010]能量采集
* ALG    :
* CMT    :
* 位于 (x,y) 的点产生的分值是 gcd(x,y) , 问题转换为求 gcd(x,y) , 答案为 Σ(gcd(x,y)*2-1)
* 考虑 gcd(x,y)=D , D<=10^5 范围不是很大 , 那么我们倒过来考虑 , 我们求解满足 gcd(x,y)=d 的 (x,y) 的个数.
* 有 Σ(gcd(x,y)*2-1) = Σ(F[d]*(d*2-1)) ;
* 其中 F[d] 表示满足 gcd(x,y)=d 的 (x,y) 的个数.
* 考虑以d为公约数的(x,y)的个数g[d]，显然有g[d]=[n/d]*[m/d] ;
* 根据容斥原理有：
* f[d]=g[d]-Σ(f[d*i])  (2<=i<=[min(n,m)/d]) ;
* 这样我们只需要倒过来从min(n,m)反推到1求解即可.
* 时间复杂度O(nlogn)
* Time   :
\****************************************/

#include <cstdio>

#define  maxn     100010LL
#define  min(x,y) ((x)<(y)?(x):(y))

typedef long long ll ;

int n , m , i , j , k ;
ll f[maxn] = {0} , ans ;

int main() {
	#define READ
	#ifdef  READ
		freopen("energy2010.in" ,"r",stdin ) ;
		freopen("energy2010.out","w",stdout) ;
	#endif
	scanf("%d%d", &n , &m ) ;
	k = min(n,m) ;
	for (i = k ; i >= 1 ; i -- ) {
		f[i] = (ll)(n/i)*(ll)(m/i) ;
		for (j = 2 ; j <= k/i ; j ++ ) f[i] -= f[i*j] ;
		ans += f[i]*(ll)(i*2-1) ;
	}
	printf("%lld\n", ans ) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}