ZOJ 3868 GCD Expectation 跟 BC39 HDU 5212 Code

ZOJ 3868 GCD Expectation 和 BC39 HDU 5212 Code

这两道题目的类型感觉是一样的都是利用了容斥的思想从后往前推然后去重。

HDU 5212 题意：

给n个数求出每个数与这n个数分别F(i)的和， F(i) = gcd(a[i], a[j]) * (gcd(a[i], a[j]) - 1).

可以这样考虑 ai与aj互质的时候F()的值是等于0 没必要计算。只要计算以i为gcd的所有的数对的个数就好了（1<=i <=10000）。

#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <cstdlib>
#include <iostream>
//#include <bits/stdc++.h>
#define MAX 0x3f3f3f3f
#define N 10005
#define mod 10007
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
#define mem(a) memset(a, 0, sizeof(a))
typedef long long ll;
using namespace std;
const double pi = acos(-1.0);

int n, v[N], dp[N], x;

int main()
{
  //freopen("in.txt","r",stdin);
  
  while(cin >> n) {
  	mem(v);
  	//mem(dp);
  	int mx = 1;
  	for(int i = 0; i < n; i++) {
  		scanf("%d", &x);
  		v[x]++;
  		mx = max(mx, x);
		}
		int ans = 0;
		for(int i = mx; i >= 1; i--) {
			dp[i] = 0;
			int cnt = 0;
			for(int j = i; j <= mx; j += i) {
				cnt += v[j];
				if(j > i) {
					dp[i] = (dp[i] - dp[j]) % mod + mod;
					dp[i] %= mod;
				}
			}
			dp[i] = (dp[i] + cnt * cnt %mod) %mod;
			int mul = i * (i-1) %mod;
			ans += mul * dp[i];
			ans %= mod;
		}
		cout << ans << endl;
	}
    
	return 0;
}

浙大校赛 GCD Expectation

题意就是求出n个数的所有子集的对应gcd的k次方。方法就是枚举1到最大值作为gcd，有多少个i的倍数统计出来为tmp , 2^tmp - 1 就一定包含了所有的gcd为i的子集但这里面可能有gcd比i大的所以要减去i的2倍及以上的个数逆序就可以统计出来。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define N 1000005
#define mod 998244353
#define MAX 0x3f3f3f3f
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
#define mem(a) memset(a,0,sizeof(a))
typedef long long ll;
using namespace std;
const double pi = acos(-1.0);

int n, v[N], x, mx, k;
ll dp[N];

ll POW(ll a, ll b) {
	ll res = 1;
	while(b) {
		if(b & 1) res = res * a %mod;
		b /= 2;
		a = a * a %mod;
	}
	return res;
}

ll solve() {
	
	ll res = 0;
	for(int i = mx; i > 0; i--) {
		dp[i] = 0;
		ll cnt = 0;
		for(int j = i; j <= mx; j += i) {
			cnt += v[j];
			if(j > i) dp[i] = ((dp[i] - dp[j]) %mod + mod) %mod; 
		}
		dp[i] += POW(2, cnt) - 1;
		dp[i] %= mod;
		res = (res %mod + dp[i] * POW(i, k) %mod) %mod;
	}
	return res;
	
}

int main()
{
  //freopen("in.txt","r",stdin);
  
  int T; cin >> T;
  while(T--) {
  	cin >> n >> k;
  	mx = 0;
  	mem(v);
  	for(int i = 0; i < n; i++) {
  		scanf("%d", &x);
  		v[x]++;
  		mx = max(mx, x);
		}
		cout << solve() << endl;
	}
    
	return 0;
}

ZOJ 3868 GCD Expectation 跟 BC39 HDU 5212 Code

相关推荐