程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 4407 Sum(容斥原理)

HDU 4407 Sum(容斥原理)

編輯：關於C++

?? 題意：一個元素為 1~n 的數列{An}，有2種操作（1000次）：

1、求某段區間 [a,b] 中與 p 互質的數的和。

2、將數列中某個位置元素的值改變。

思路：先預處理求出1到400000所有數的質因子保存起來。

這個問題可以轉化為求[1,R]之間與p不互素的數的和，這個可以用容斥原理來做，然後用區間和減去這個值就是答案，這是靜態的做法。

如果有修改的話，我們注意到修改次數很少，可以把所有修改用map存起來，對於當前的每次操作，把之前的修改遍歷一遍就可以了，時間復雜度為O(m*m*logn)。

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
#define eps 1e-6 
#define LL long long  
using namespace std;  

const int maxn = 500000;
//const int INF = 0x3f3f3f3f;
LL su[maxn];
bool vis[maxn];
map ms;
vector prime[maxn];
void init() {
	su[0] = 0;
	for(int i = 1; i <= 400000; i++) su[i] = su[i-1] + i;
	memset(vis, 0, sizeof(vis));
	for(int i = 2; i <= 400000; i++) if(!vis[i]) {
		for(int j = i; j <= 400000; j+=i) vis[j] = 1, prime[j].push_back(i);
	}
}
int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a%b);
}
int n, m;
LL solve(int n, int p) {
	LL ans = 0;
	int sz = prime[p].size();
	int s = (1< n) continue;
		int num = n/tmp;
		ans = ans + (LL)cnt*((LL)tmp+(LL)num*(LL)tmp)*(LL)num/2;
	}
	return ans;
}
int main() {
	//freopen(input.txt, r, stdin);
	int T; cin >> T;
	init();
	while(T--) {
		cin >> n >> m;
		ms.clear();
		int op;
		for(int i = 0; i < m; i++) {
			scanf(%d, &op);
			if(op == 1) {
				int l, r, p; scanf(%d%d%d, &l, &r, &p);
				LL ans = solve(r, p)-solve(l-1, p);
				//cout << ans << endl;
				for(map::iterator it = ms.begin(); it != ms.end(); it++) {
					if(it->first>=l && it->first<=r) {
						if(gcd(it->first, p) != 1) ans -= it->first;
						if(gcd(it->second, p) != 1) ans += it->second;
						ans += it->first - it->second;
					}
				}
				//cout << ans << endl;
				//cout << su[r] << endl << su[l-1] << endl;
				cout << su[r]-su[l-1]-ans << endl;
			}
			else {
				int p, v; scanf(%d%d, &p, &v);
				ms[p] = v;
			}
		}
	} 
	return 0;
}