1101: [POI2007]Zap(莫比乌斯反演)
2024-08-27 07:29:24
1101: [POI2007]Zap
Time Limit: 10 Sec Memory Limit: 162 MB
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)。
/*
莫比乌斯反演.
随便搞一搞就好了。。。
用long long 会T
用cout 会 R
不知道为啥.
*/
#include<iostream>
#include<cstdio>
#define MAXN 50001
int ans,sum[MAXN],last;
int mu[MAXN],tot,pri[MAXN];
bool vis[MAXN];
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
void pre()
{
mu[1]=1;
for(int i=2;i<=MAXN-1;i++)
{
if(!vis[i]) vis[i]=true,pri[++tot]=i,mu[i]=-1;
for(int j=1;j<=tot&&i*pri[j]<=MAXN-1;j++)
{
if(!vis[i*pri[j]]) vis[i*pri[j]]=true;
if(i%pri[j]) mu[i*pri[j]]=-mu[i];
else {mu[i*pri[j]]=0;break ;}
}
}
for(int i=1;i<=MAXN-1;i++) sum[i]=sum[i-1]+mu[i];
return ;
}
void slove(int n,int m,int k)
{
ans=0;n/=k,m/=k;
for(int i=1;i<=min(n,m);i=last+1)
{
last=min(n/(n/i),m/(m/i));
ans+=(n/i)*(m/i)*(sum[last]-sum[i-1]);
}
printf("%d\n",ans);
return ;
}
int main()
{
int t,n,m,k;
pre();t=read();
while(t--)
{
n=read(),m=read(),k=read();
slove(n,m,k);
}
return 0;
}
最新文章
- 安装Jenkins
- digitalocean添加ssh_keys
- quick lua目录结构
- web错误
- Linux内核基础--事件通知链(notifier chain)
- HDU-4661 Message Passing 树形DP,排列组合
- (重刷)HDU 1874 畅通工程续 + HDU 2544 最短路 最短路水题,dijkstra解法。
- day05
- MessageBox不能前置显示的问题
- 用 Python 脚本实现对 Linux 服务器的网卡流量监控
- 动态规划略有所得 数字三角形(POJ1163)
- PL/SQL + Oracle客户端 配置记录
- 全局光照:光线追踪、路径追踪与GI技术进化编年史
- 张高兴的 Xamarin.Android 学习笔记:(一)环境配置
- 常用Oracle进程资源查询语句(运维必看)
- CRM/PLM/SCM/MES与ERP的联系与区别
- Win10, VS2017环境下OpenCV3.4.2的配置
- numpy delete
- C#//字节数组转16进制字符串
- The Moon and Sixpence摘抄