算法:
利用数据1...N的性质，求与P的互质的个数，位运算，容斥定理。。
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream> #include<vector> #include<string> #include<math.h> #include<map> #include<set> #include<algorithm> using namespace std;struct info {int s,e,p,num; }seg[1010];struct pinfo {int id, v, num; }p[1010];int factor[1000]; //保存因子 map<int,int>mp;int gcd( int n, int m ) {return m ? gcd(m, n % m ) : n; }//容斥定理求互质之和 long long cal( int x, int n) {//分解出x的因子if( x == 0 )return 0;int i,Lim = sqrt( x * 1.0 ), cnt = 0;for( i = 2; i <= Lim; i++){if( x % i == 0 ){factor[++cnt] = i;while( x % i == 0 )x = x / i; } }if( x != 1 ){factor[++cnt] = x; }int mask = 1 << cnt;long long ans = 0;for( int i = 1; i < mask; i++){ int tt = 0, fac = 1, k;for( int j = 0; j < cnt; j++){if( i & (1<<j) ){tt++;fac *= factor[j+1];} }//如果是奇数项 if( tt & 1 ){k = n / fac;ans += ( fac + 1LL * fac * k ) * k / 2;} else{k = n / fac;ans -= ( fac + 1LL * fac * k ) * k / 2; } } return ans; }int main( ) {int N, M, a, b, c, d, c1, c2, T;scanf("%d",&T);while( T-- ){ scanf("%d%d",&N,&M);c1 = c2 = 0;for( int i = 1; i <= M; i++){scanf("%d",&a);if( a == 1 ){scanf("%d%d%d",&seg[c1].s, &seg[c1].e, &seg[c1].p);seg[c1].num = i; c1++;}else{scanf("%d%d",&p[c2].id, &p[c2].v);p[c2].num = i;c2++; } } long long x, y, pans;for( int i = 0; i < c1; i++) //枚举每一个查询 {x = cal(seg[i].p, seg[i].s-1);y = cal(seg[i].p, seg[i].e);pans = ((1 + seg[i].e * 1LL) * seg[i].e * 1LL / 2 - y ) - (1 + seg[i].s - 1 ) * 1LL * (seg[i].s - 1) * 1LL / 2 + x;mp.clear();for( int j = 0; j < c2; j++){if( p[j].num < seg[i].num && seg[i].e >= p[j].id && seg[i].s <= p[j].id ){mp[p[j].id] = p[j].v; }else if( p[j].num > seg[i].num )break; }map<int,int>::iterator it;for( it = mp.begin(); it != mp.end(); it++){int xx = gcd(seg[i].p, it->second);int yy = gcd(seg[i].p, it->first);if( yy == 1 && xx != 1 )pans -= it->first;else if( yy != 1 && xx == 1 )pans += it->second; else if( yy == 1 && xx == 1 )pans += it->second - it->first; } printf("%I64d\n", pans); }}return 0; }
