bzoj1101

1101: [POI2007]Zap

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2319  Solved: 936
[Submit][Status][Discuss]

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

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

6,3),(3,3)。

HINT

Source

http://blog.csdn.net/ycdfhhc/article/details/50637101 讲得很详细

就是用那个奇怪的公式套一下,然后化成可接受复杂度的式子(废话)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 50010
int sum[N],mu[N],pri[N],mark[N];
void INIT()
{
    mu[1]=1; int tot=0;
    for(int i=2;i<=50000;i++)
    {
        if(!mark[i])
        {
            mu[i]=-1;
            pri[++tot]=i;
        }
        for(int j=1;j<=tot&&pri[j]*i<=50000;j++)
        {
            mark[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                mu[i*pri[j]]=0;
                break;
            }
            mu[i*pri[j]]=-mu[i];
        }
    }
    for(int i=1;i<=50000;i++)
    {
        sum[i]=sum[i-1]+mu[i];
    }
}
void solve(int a,int b)
{
    int ans=0;
    if(a>b) swap(a,b);
    for(int l=1,r=0;l<=a;l=r+1)
    {
        r=min(a/(a/l),b/(b/l));
        ans+=(sum[r]-sum[l-1])*(a/l)*(b/l);
    }
    printf("%d\n",ans);
}
int main()
{
    INIT();
    int T; scanf("%d",&T);
    while(T--)
    {
        int a,b,d; scanf("%d%d%d",&a,&b,&d);
        solve(a/d,b/d);
    }
    return 0;
}

时间: 01-19

bzoj1101的相关文章

Bzoj1101 [POI2007]Zap

Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 2414  Solved: 995[Submit][Status][Discuss] Description FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d.作为FGD的同学,FGD希望得到你的帮助. Input 第一行包含一个正整数n,表示一共有n组询问.(1<=n<= 50000)接下

【Poi2007】【Bzoj1101】Zap

先膜一发黄学长的题解,http://hzwer.com/4205.html 来一步步推 令a'=a/d b'=b/d 首先,原来要求的东西= 再利用莫比乌斯函数的性质可以得出 这里需要用到分块的思想,具体看程序里. 个人觉得(a/(a/i))非常妙 接下来问题就变成了一段段连续的了, 维护莫比乌斯函数的前缀和,就好了 1 #include<cstdio> 2 #include<algorithm> 3 #define ll long long 4 using namespace s

【莫比乌斯反演】BZOJ1101 [POI2007]zap

Description 回答T组询问,有多少组gcd(x,y)=d,x<=a, y<=b.T, a, b<=4e5. Solution 显然对于gcd=d的,应该把a/d b/d,然后转为gcd=1计算 计算用莫比乌斯反演相信大家都会 关键是有T组询问n^2会T 于是有这样一个优化可以做到每次sqrt(n) 每一次是ret+=mu[i]*(n/i)*(m/i) 可是除法向下取整所以会导致很多i的(n/i)*(m/i)一样 具体来说,向下取整得到的结果一定是约数所以对于(n/i)最多2sq

【BZOJ】2820: YY的GCD(莫比乌斯)

http://www.lydsy.com/JudgeOnline/problem.php?id=2820 此题非常神! 下文中均默认n<m 首先根据bzoj1101的推理,我们易得对于一个数d使得数对(x,y)=k的个数为: $$\sum_{1<=d<=n'} \mu (d) \times \lfloor \frac{n}{d} \rfloor \times \lfloor \frac{m}{d} \rfloor, 其中n'=\lfoor \frac{n}{k} \rfloor$$ 所以

【BZOJ2301】【HAOI2011】Problem b [莫比乌斯反演]

Problem b Time Limit: 50 Sec  Memory Limit: 256 MB[Submit][Status][Discuss] Description 对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数. Input 第一行一个整数n,接下来n行每行五个整数,分别表示a.b.c.d.k Output 共n行,每行一个整数表示满足要求的数对(x,y)的个数. Sample Inp

(转载)关于gcd的8题

发现其实有关gcd的题目还是挺多的,这里根据做题顺序写出8题. [bzoj2818: Gcd] gcd(x,y)=质数, 1<=x,y<=n的对数 做这题的时候,懂得了一个非常重要的转化:求(x, y) = k, 1 <= x, y <= n的对数等于求(x, y) = 1, 1 <= x, y <= n/k的对数!所以,枚举每个质数p(线性筛素数的方法见:线性时间内筛素数和欧拉函数),然后求(x, y) = 1, 1 <= x, y <= n/p的个数.