希望更丰富的展现？使用Markdown
by StarKnight @ 2019-08-05 10:34:11
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
unsigned int N,mod=2147483648ll;
struct inc
{
unsigned int m,n,a,id;
}k[20100];
struct lom
{
unsigned int r,id;
}f[100100];
unsigned int t,vis[100100],mu[100100],pri[9600],pn,fm[100100],maxn,j=1,g[100100],gt[400100],ans[20100],z[100100];
bool cmp2(inc x,inc y){return x.a<y.a;}
bool cmp1(lom x,lom y){return x.r<y.r;}
void read(unsigned int &x)
{
bool f=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-') f=1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
(f)&&(x=-x);
}
void print(unsigned int x)
{
if(x<0){putchar('-');x=-x;}
if(x>=10) print(x/10);
putchar(x%10+'0');
}
void change(int w,int l,int r,int b,unsigned int c)
{
if(r<b||l>b) return;
if(l==r)
{
g[b]=(g[b]+c);
gt[w]=(gt[w]+c);
return;
}
int mid=(l+r)/2;
change(w<<1,l,mid,b,c);
change(w<<1|1,mid+1,r,b,c);
gt[w]=(gt[w<<1]+gt[w<<1|1]);
}
unsigned int ask(int w,int l,int r,int x,int y)
{
if(l>y||r<x) return 0;
if(l>=x&&r<=y) return gt[w];
int mid=(l+r)/2;
return (ask(w<<1,l,mid,x,y)+ask(w<<1|1,mid+1,r,x,y));
}
int main()
{
f[1].id=f[1].r=fm[1]=mu[1]=1;
for(int i=2;i<=100000;i++)
{
if(vis[i]==0)
{
mu[i]=-1;
pri[++pn]=i;
z[i]=i+1;
f[i].id=i;
f[i].r=i+1;
}
for(int j=1;j<=pn;j++)
{
int lk=pri[j]*i;
if(lk>100000) break;
vis[lk]=1;
if(i%pri[j]==0)
{
z[lk]=z[i]*pri[j]+1;
f[lk].r=f[i].r/z[i]*z[lk];
f[lk].id=lk;
break;
}
else
{
mu[lk]=-mu[i];
z[lk]=pri[j]+1;
f[lk].r=f[i].r*f[pri[j]].r;
f[lk].id=lk;
}
}
fm[i]=fm[i-1]+mu[i];
}
sort(f+1,f+100001,cmp1);
cin>>t;
for(int i=1;i<=t;i++)
{
read(k[i].n);
read(k[i].m);
read(k[i].a);
if(k[i].n>k[i].m){int temp=k[i].n;k[i].n=k[i].m;k[i].m=temp;}
k[i].id=i;
N=max(N,k[i].n);
}
sort(k+1,k+t+1,cmp2);
for(int i=1;i<=t;i++)
{
for(;f[j].r<=k[i].a&&j<=100000;j++)
for(int l=f[j].id;l<=N;l+=f[j].id)//g[l]+=mu[l/f[j].id]*f[j].r;
change(1,1,N,l,mu[l/f[j].id]*f[j].r);
int last;
for(int l=1;l<=k[i].n;l=last+1)
{
last=min(k[i].n/(k[i].n/l),k[i].m/(k[i].m/l));
ans[k[i].id]=(ans[k[i].id]+(k[i].n/l)*(k[i].m/l)*ask(1,1,N,l,last));
}
}
for(int i=1;i<=t;i++)
{
print(ans[i]&(~(1<<31)));
putchar('\n');
}
return 0;
}
by octives @ 2019-08-05 10:36:42
卡常加这个
```cpp
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <immintrin.h>
#include <emmintrin.h>
```
by Del_Your_Heart @ 2019-08-05 10:42:25
没想到你也是基金会会员
by 星尘舰队 @ 2019-08-05 10:43:49
@[Del_Your_Heart](/space/show?uid=62246) 还是T了三个点
by octives @ 2019-08-05 11:03:29
@[猪肉脱皮](/space/show?uid=40153) 加懒标记啊，不然复杂度高，过不了
by Del_Your_Heart @ 2019-08-05 11:15:14
@[Del_Your_Heart](/space/show?uid=62246) 单点修改，区间查询怎么用懒标记？
by octives @ 2019-08-05 11:19:11
@[猪肉脱皮](/space/show?uid=40153) 单点修改这种事为什么不用树状数组
by Del_Your_Heart @ 2019-08-05 11:23:09
@[猪肉脱皮](/space/show?uid=40153) 线段树常数大
by Del_Your_Heart @ 2019-08-05 11:23:33
@[猪肉脱皮](/space/show?uid=40153) $for$循环里用$register$ $int$，函数前加$inline$，把$something++$改为$++something$试一下（能卡的都卡了）
by Del_Your_Heart @ 2019-08-05 11:26:46