在你以为理解mobus的时候，苦苦想通过化简公式来降低复杂度时，这题又打了我一巴掌。
看来我并没有理解到acmicpc比赛的宗旨啊。
这么多次查询可以考虑离线操作，使用树状数组单点更新。
/************************************************************** Problem: 3529 User: chenhuan001 Language: C++ Result: Accepted Time:5264 ms Memory:8412 kb ****************************************************************/ #include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> using namespace std; #define N 100100 long long getpow(int j,int cnt) { return (long long)(pow((double)j, cnt+1)-1)/(j-1); } struct Binary_Index_tree { long long a[N+1]; void init() { memset(a,0,sizeof(a)); } //位运算 int lowbit(int x) { return x & (-x); } //修改x这个点，并把所有包含x点的所有点都进行修改 void modify(int x,int add) { if(x==0) return ; while(x<N) { a[x]+=add; x+=lowbit(x); } } //得到[1,x]的和 long long get_sum(int x) { //if(x >= N) return 0; long long ret=0; while(x>0) { ret += a[x]; x-=lowbit(x); } return ret; } }bt; struct Case { int id; int n,m,a; }tt[202000]; struct Link { int i,x; }g[N+1]; long long ans[202000]; int casecmp(Case t1,Case t2) { return t1.a<t2.a; } int linksort(Link l1,Link l2) { return l1.x<l2.x; } //－－莫比乌斯反演函数－－// //说明：利用线性素数筛选顺便求了个mu //注释部分为求从区间[1,b]和区间[1,d]中取两个数，互质对数O（n^0.5） //复杂度:O(n) int mu[N]; //int sum[N]; void mobus() { bool mark[N]; int prime[N]; int pcnt=0; memset(mark,0,sizeof(mark)); mu[1] = 1; for(int i=2;i<N;i++) { if(mark[i] == 0) { prime[pcnt++] = i; mu[i] = -1; } for(int j=0;j<pcnt && i*prime[j]<N;j++) { int tmp = i*prime[j]; mark[tmp] = 1; if( i%prime[j] == 0 ) { mu[tmp] = 0; break; } mu[tmp] = mu[i]*-1; } } // for(int i=1;i<N;i++) // sum[i] += sum[i-1]+mu[i]; } long long gaobili(int b,int d) { if(b<=0||d<=0) return 0; int m = min(b,d); long long ans = 0; while(m>=1) { int tb = b/( b/m +1 )+1; int td = d/( d/m +1 )+1; //前进的最大位置 int tm = max(tb,td); ans += (bt.get_sum(m)-bt.get_sum(tm-1))*(b/m)*(d/m); m = tm-1; } return ans; } int main(int argc, const char * argv[]) { for(int i=1;i<N;i++) { int tmp = 1; int ti = i; for(int j=2;j*j<=ti;j++) { if(ti%j == 0) { int cnt=0; while(ti%j==0) { ti /= j; cnt++; } tmp *= getpow(j,cnt); } } if(ti != 1) { tmp *= getpow(ti,1); } g[i].i = i; g[i].x = tmp; } sort(g+1,g+N,linksort); int T; cin>>T; for(int i=0;i<T;i++) { tt[i].id = i; scanf("%d%d%d",&tt[i].n,&tt[i].m,&tt[i].a); } sort(tt,tt+T,casecmp); bt.init(); mobus(); int j=1; for(int i=0;i<T;i++) { while(j<N && g[j].x <= tt[i].a) { int tmp = g[j].i; for(int d=tmp;d<N;d += tmp) { bt.modify(d, g[j].x*mu[d/tmp]); } j++; } //然后就是根号n ans[tt[i].id] = gaobili(tt[i].m, tt[i].n); } //for(int i=0;i<T;i++) cout<<ans[i]%(1LL<<31)<<endl; long long mod = (1LL<<(31LL)); for(int i=0;i<T;i++) printf("%d ",(int)(ans[i]&(0x7fffffff))); return 0; }