[Noi2010]能量采集
ztx
posted @ 2015年1月13日 19:37
in 容斥原理
, 359 阅读
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | /****************************************\* 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 :\****************************************/ |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | /****************************************\* 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 ;} |
评论 (0)