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

n+e

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

 
 
 

日志

 
 

[BZOJ1101][POI2007]Zap  

2015-01-29 13:38:11|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1101: [POI2007]Zap

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1393  Solved: 452
[Submit][Status]

Description

FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d。作为FGD的同学,FGD希望得到你的帮助。

Input

第一行包含一个正整数n,表示一共有n组询问。(1<=n<= 50000)接下来n行,每行表示一个询问,每行三个正整数,分别为a,b,d。(1<=d<=a,b<=50000)

Output

对于每组询问,输出到输出文件zap.out一个正整数,表示满足条件的整数对数。

Sample Input

2
4 5 2
6 4 3

Sample Output

3
2

HINT

对于第一组询问,满足条件的整数对有(2,2),(2,4),(4,2)。对于第二组询问,满足条件的整数对有(6,3),(3,3)。

Solution

[BZOJ1101][POI2007]Zap - Trinkle - n+e

Code

/**************************************************************
    Problem: 1101
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:5912 ms
    Memory:9812 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<<23],*O=buf,stk[100];int ts;
inline 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,d,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(a/d,b/d)))
    a=F(),b=F(),d=F();
    *--O=0,puts(buf);
}
  评论这张
 
阅读(21)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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