[Sdoi2014]数表

 

2133. [SDOI2014] 数表

★★★☆   输入文件：sdoi2014shb.in   输出文件：sdoi2014shb.out   简单对比
时间限制：5 s   内存限制：512 MB

【题目描述】

有一张N×m的数表，其第i行第j列(1<=i<=n,1<=j<=m)(1<=n,m<=10^5,1<=Q<=2×10^4)的数值为能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。

【输入格式】

输入包含多组数据。输入的第一行一个整数Q表示测试点内的数据组数，接下来Q行，每行三个整数n，m，a(|a| < =10^9)描述一组数据。

【输出格式】

对每组数据，输出一行一个整数，表示答案模2^31的值。

【样例输入】

 

2

4 4 3

10 10 5

 

【样例输出】

 

20

148

 

【来源】

SDOI2014day1

 

2017-03-07 21:33:54

终于把坑填起来了。

//COGS RANK1
#include<cstdio>
#include<algorithm>
#define pir pair<int,int>
#define fi first
#define se second
#define EF if(ch==EOF) return EOF;
#define EX if(ch==EOF) return x*f;
using namespace std;
const int N=1e5+5;
struct node{int n,m,a,id;}q[N];
int T,tot,mx,prime[N/3],mu[N],BIT[N],ans[N];
bool check[N];pir F[N];
inline int read(){
    int x=0,f=1;char ch=getchar();EF
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();EF}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();EX}
    return x*f;
}
inline bool operator <(const node &a,const node &b){
    return a.a<b.a;
}
inline int lowbit(int x){
    return x&-x;
}
inline void update(int x,int v){
    for(int i=x;i<=mx;i+=lowbit(i)) BIT[i]+=v;
}
inline int query(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=BIT[i];
    return res;
}
void prepare(){
    mu[1]=1;
    for(int i=2;i<=mx;i++){
        if(!check[i]) prime[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&prime[j]*i<=mx;j++){
            check[prime[j]*i]=1;
            if(i%prime[j]==0){mu[prime[j]*i]=0;break;}
            else mu[prime[j]*i]=-mu[i];
        }
    }
    for(int i=1;i<=mx;i++){
        for(int j=i;j<=mx;j+=i){
            F[j].fi+=i;
        }
    }
    for(int i=1;i<=mx;i++) F[i].se=i;
}
inline void solve(int mom){
    int id=q[mom].id,n=q[mom].n,m=q[mom].m;
    for(int i=1,pos;i<=n;i=pos+1){
        pos=min(n/(n/i),m/(m/i));
        ans[id]+=(n/i)*(m/i)*(query(pos)-query(i-1));
    }
}
int main(){
    freopen("sdoi2014shb.in","r",stdin);
    freopen("sdoi2014shb.out","w",stdout);
    T=read();
    for(int i=1;i<=T;i++){
        q[i].n=read();q[i].m=read();q[i].a=read();q[i].id=i;
        if(q[i].n>q[i].m) swap(q[i].n,q[i].m);
        mx=max(mx,q[i].n);
    }
    prepare();
    sort(q+1,q+T+1);
    sort(F+1,F+mx+1);
    int now=0;
    for(int i=1;i<=T;i++){
        while(now+1<=mx&&F[now+1].fi<=q[i].a){
            now++;
            for(int j=F[now].se;j<=mx;j+=F[now].se){
                update(j,F[now].fi*mu[j/F[now].se]);
            }
        }
        solve(i);
    }
    for(int i=1;i<=T;i++) printf("%d\n",ans[i]&0x7fffffff);
    return 0;
}