注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2301][HAOI2011]Problem b  

2015-01-29 17:44:02|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2301: [HAOI2011]Problem b

Time Limit: 50 Sec  Memory Limit: 256 MB
Submit: 1471  Solved: 612
[Submit][Status]

Description

对于给出的n个询问,每次求有多少个数对(x,y),满足axbcyd,且gcd(x,y) = kgcd(x,y)函数为xy的最大公约数。

Input

第一行一个整数n,接下来n行每行五个整数,分别表示abcdk

Output

n行,每行一个整数表示满足要求的数对(x,y)的个数

Sample Input

2
2 5 1 5 1
1 5 1 5 2

Sample Output

14
3

HINT

100%的数据满足:1≤n≤50000,1≤a≤b≤50000,1≤c≤d≤50000,1≤k≤50000

Solution


[BZOJ1101][POI2007]Zap - Trinkle - n+e
剩下的就是前缀相减了

Code

/**************************************************************
    Problem: 2301
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:9720 ms
    Memory:2648 kb
****************************************************************/
 
#include<cstdio>
#define N 50010
inline int getc(){
    static char buf[1<<15],*S=buf,*T=buf;
    if(S==T)if(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)return 0;
    return*S++;
}
int aa,ch;inline int F(){
    while(ch=getc(),ch<48||ch>57);aa=ch-48;
    while(ch=getc(),ch>47&&ch<58)aa=aa*10+ch-48;return aa;
}
char buf[1<<20],*O=buf,stk[30];int ts;
void P(int x){
    if(!x)*O++=48;
    else{
        for(ts=0;x;x/=10)stk[++ts]=x%10;
        for(;ts;*O++=48+stk[ts--]);
    }
    *O++='\n';
}
int n,miu[N],vis[N],sum[N],i,j,a,b,c,d,x,p[N],t,l,r,t0,t1,ans;
#define min(a,b) (a<b?a:b)
int calc(int n,int m)
{
    for(i=min(n,m),l=1,ans=0;l<=i;l=r+1)
    {
        t0=n/l,t1=m/l;
        r=min(n/t0,m/t1);
        ans+=(sum[r]-sum[l-1])*t0*t1;
    }
    return ans;
}
int main()
{
    for(n=50000,miu[1]=sum[1]=1,i=2;i<=n;sum[i]=sum[i-1]+miu[i],i++)
    {
        if(!vis[i])p[++t]=i,miu[i]=-1;
        for(j=1;j<=t&&p[j]*i<=n;j++)
        {
            vis[i*p[j]]=1;
            if(i%p[j]==0)
            {
                miu[i*p[j]]=0;
                break;
            }
            else miu[i*p[j]]=-miu[i];
        }
    }
    for(t=F();t--;P(calc(b/x,d/x)+calc((a-1)/x,(c-1)/x)-calc((a-1)/x,d/x)-calc(b/x,(c-1)/x)))
    a=F(),b=F(),c=F(),d=F(),x=F();
    *--O=0,puts(buf);
}
  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018