bzoj1101
2024-10-20 15:54:33
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
4 5 2
6 4 3
Sample Output
3
2
//对于第一组询问,满足条件的整数对有(2,2),(2,4),(4,2)。对于第二组询问,满足条件的整数对有(
6,3),(3,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[]=; int tot=;
for(int i=;i<=;i++)
{
if(!mark[i])
{
mu[i]=-;
pri[++tot]=i;
}
for(int j=;j<=tot&&pri[j]*i<=;j++)
{
mark[i*pri[j]]=;
if(i%pri[j]==)
{
mu[i*pri[j]]=;
break;
}
mu[i*pri[j]]=-mu[i];
}
}
for(int i=;i<=;i++)
{
sum[i]=sum[i-]+mu[i];
}
}
void solve(int a,int b)
{
int ans=;
if(a>b) swap(a,b);
for(int l=,r=;l<=a;l=r+)
{
r=min(a/(a/l),b/(b/l));
ans+=(sum[r]-sum[l-])*(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 ;
}
最新文章
- .NET中那些所谓的新语法之三:系统预定义委托与Lambda表达式
- Mongoose学习笔记
- 较友好的Web文件下载用户体验实例
- 获取iOS系统版本 --- UIDevice
- input[type=text]点击之后无边框, 一进页面就显示光标
- 通达OA 公共文件柜二次开发添加管理信息(图文)
- Linux自动修改IP脚本(手动编写)
- 【SoDiaoEditor更新啦】--谨以献给那些还在医疗行业奋斗的小伙伴们
- Javascript中的闭包 O__O ";…
- css3修改滚动条样式
- spring boot学习笔记2
- Spark学习笔记--Spark在Windows下的环境搭建
- CefSharp v62修改,支持.net4.0
- 动态加载与插件系统的初步实现(一):反射与MEF解决方案
- sqlplus rlwrap readline
- 第8章 Linux磁盘与文件系统管理
- 第十六章 IIC协议详解+UART串口读写EEPROM
- MySQL的数据库引擎的类型(转)
- BZOJ 1132 [POI2008]Tro(极角排序)
- is is not == !=之间的区别
热门文章
- SQL SERVER 2012 第四章 连接 JOIN语句的早期语法结构 &; 联合UNION
- vs npm设置淘宝npm
- 碧砚适合佳能328 4452 ICD520 4472 4450 硒鼓4700一体机墨盒4770
- GAN Generative Adversarial Network 生成式对抗网络-相关内容
- chapter1:using neural nets to recognize handwritten digits
- poj 1695 Magazine Delivery 记忆化搜索
- DataGridView依据下拉列表显示数据
- soapUI系列之—-06 testrunner实现自动化测试
- JNI/NDK开发指南(2)
- jquery源码学习笔记二:jQuery工厂