3529: [Sdoi2014]数表

Time Limit: 10 Sec  Memory Limit: 512 MB

Submit: 1399  Solved: 694

[][][]

Description

    有一张N×m的数表，其第i行第j列（1 < =i < =礼，1 < =j < =m）的数值为

能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。

Input

    输入包含多组数据。

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

Output

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

Sample Input

2

4 4 3

10 10 5

Sample Output

20

148

HINT

1 < =N．m < =10^5  ， 1 < =Q < =2×10^4

Source

---

 

一个位置的答案就是gcd(i,j)的约数和

一个个单独算不好优化不行，从gcd(i,j)的取值方面考虑，因为它的取值就是1...n

设F(i)为i的约数和，f(i)为gcd(x,y)=i的个数，那么答案就是ΣF(i)*f(i)

f(i)上两题用到过，反演后f(i)=Σ{i|d} miu(d/i)*(n/d)*(m/d)

d和i的取值范围相同，可以得到如下式子

现在我们只需要求出g(i)=的前缀和 这个问题就能在O(√n)的时间内出解

F(i)是约数和函数，可以通过线性筛计算，或者直接nlogn暴力枚举倍数，速度差不多

然后和上一题一样，暴力枚举每个i更新它的倍数

那么a的限制如何处理？考虑离线

我们发现对答案有贡献的i只有F(i)<=a的i 那么我们将询问按照a从小到大排序 将F(i)从小到大排序 每次询问将<=a的F(i)按照枚举倍数更新的方式插入 用树状数组来维护g的前缀和  这样枚举倍数logn，每个倍数插入树状数组logn，总共nlog^2n

本题取模有一种好厉害的做法：自然溢出int,最后&0x7FFFFFFF

复杂度O(nlog^2n+q√nlogn)

 

注意:排序[1,N)的话是sort(a+1,a+N),不要a+N+1.......

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;const int N=1e5+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}struct ques{    int n,m,a,id;    bool operator <(const ques &r)const{
    return a
           
            m) swap(n,m); for(int i=1;i<=n;i=r+1){ r=min(n/(n/i),m/(m/i)); ans+=(sum(r)-sum(i-1))*(n/i)*(m/i); } return ans;}int ans[N];int main(int argc, const char * argv[]){ sieve(); sort(sf+1,sf+N);//!!!!! int 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; sort(q+1,q+1+T); int now=1; for(int i=1;i<=T;i++){ int a=q[i].a; for(;sf[now].s<=a;now++) ins(now); ans[q[i].id]=cal(q[i].n,q[i].m)&0x7FFFFFFF; } for(int i=1;i<=T;i++) printf("%d\n",ans[i]); return 0;}
           
          
         
        
       
      

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;const int N=1e5+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}struct ques{    int n,m,a,id;    bool operator <(const ques &r)const{
    return a
           
            m) swap(n,m); for(int i=1;i<=n;i=r+1){ r=min(n/(n/i),m/(m/i)); ans+=(sum(r)-sum(i-1))*(n/i)*(m/i); } return ans;}int ans[N];int main(int argc, const char * argv[]){ sieve(); sort(sf+1,sf+100000); int 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; sort(q+1,q+1+T); int now=1; for(int i=1;i<=T;i++){ int a=q[i].a; for(;now<=100000&&sf[now].s<=a;now++) ins(now); ans[q[i].id]=cal(q[i].n,q[i].m)&0x7FFFFFFF; } for(int i=1;i<=T;i++) printf("%d\n",ans[i]); return 0;}