codeforces983A(数学题)
1 second
256 megabytes
standard input
standard output
You are given several queries. Each query consists of three integers pp, qq and bb. You need to answer whether the result of p/qp/q in notation with base bb is a finite fraction.
A fraction in notation with base bb is finite if it contains finite number of numerals after the decimal point. It is also possible that a fraction has zero numerals after the decimal point.
The first line contains a single integer nn (1≤n≤1051≤n≤105) — the number of queries.
Next nn lines contain queries, one per line. Each line contains three integers pp, qq, and bb (0≤p≤10180≤p≤1018, 1≤q≤10181≤q≤1018, 2≤b≤10182≤b≤1018). All numbers are given in notation with base 1010.
For each question, in a separate line, print Finite if the fraction is finite and Infinite otherwise.
2
6 12 10
4 3 10
Finite
Infinite
4
1 1 2
9 36 2
4 12 3
3 5 4
Finite
Finite
Finite
Infinite
612=12=0,510612=12=0,510
43=1,(3)1043=1,(3)10
936=14=0,012936=14=0,012
412=13=0,13412=13=0,13
题意:给出一个分式q/p,求在b进制下q/p得到的小数是否有限。
思路:首先对于我们熟悉的十进制下,如果一个数除的尽另一个数,当且仅当分母的所有质因子集合为分子的质因子集合的子集,因为分子除以分母得到的是一个小数,而有尽的小数可以看成是一个整数(乘以对应小数点后数字位数的10的对应次方)(假设小数点后有n位,那么就乘以10的n次方),这样就把问题简化为求十进制下一个数是否可以整除另一个数的问题。而分子可以有限的在需要的情况下可以乘10再乘10^(-1)(对应的增加10的质因子2,5来抵消分母的质因子2或5)。
例:3/16==3/(2*2*2*2)==(3*10*10*10*10)/(2*2*2*2)*10^(-4)==(3*5*2*5*2*5*2*5*2)/(2*2*2*2)*10^(-4)==(3*5*5*5*5)*10^(-4)==1875*10(-4)==0.1875
4/80-->先化简(分子分母同时除以他们的最大公因数)-->1/20==1/(2*2*5)==(1*10*10)/(2*2*5)*10^(-2)==(1*2*5*2*5)/(2*2*5)*10^(-2)==5*10^(-2)==0.05
1/12==1/(2*2*3)==(1*10*10)/(2*2*3)*10^(-2)==(1*2*5*2*5)/(2*2*3)*10^(-2)==(1*5*5)/3*10^(-2),此时我们可以发现我们不能以分子乘10的方法来消去分母的3,因为3不是10的质因子,所以1/12除不尽。
综上,推广到n进制的情况下,先化简分子与分母后,分母化成最小质因子乘积的状态下,如果分母的所有的质因子都可以在n的质因子集合里找到(相当于是分母质因子集合是n的质因子集合的子集)它就可以除的尽(因为可以对应的乘n来抵消分母与n共同的质因子)。
代码:
#include<stdio.h>
#define ll __int64
ll gcd(ll a,ll b)//求最大公约数
{
ll r;
while(b)
{
r=a%b;
a=b;
b=r;
}
return a;
}
int main()
{
int n;
scanf("%d",&n);
ll p,q,b;
while(n--)
{
scanf("%d%d%d",&p,&q,&b);
if(p==0)//任何数除以0后等于0
printf("Finite\n");
else
{
ll c=gcd(p,q);
p=p/c;
q=q/c;
ll g;
while(b%q)//剔除分母q与b的共同质因子
{
g=gcd(q,b);
if(g==1)
break;
q=q/g;
b=g; //因为q与b的最大公因数是g,当q/g后,剩余的数与b的公因数只会在g中,以此来缩小范围
}
if(b%q==0)//如果b%q==0,说明在剔除后,q所有剩余的质因子都可以在剩余的b的质因子中找到
printf("Finite\n");
else
printf("Infinite\n");
}
}
return 0;
}
最新文章
- JavaScript Patterns 5.6 Static Members
- jQuery validate 验证隐藏域
- C#集合 -- Equality和Order插件
- asp.net中绘制大数据量的可交互的图表
- hibernate.properties
- 【暑假】[基本数据结构]根据BFS与DFS确定树
- LC-检索
- BigDecimal用法详解(转)
- Linux下select函数的使用
- jquery序列化form表单
- 编写第一个Flutter App(翻译)
- dskinlite(uieasy mfc界面库)使用记录4:绘制动态元素(listbox)
- Luogu4512 【模板】多项式除法(多项式求逆+NTT)
- Codeforces 483B - Friends and Presents(二分+容斥)
- 实现锁死的有滚动条的div的表格(datagird)
- MVC v5.1 Preview 包含 web api 2.1 web pages 3.1
- [CF1043G]Speckled Band
- POJ 3237 Tree (树链剖分)
- django 连接mysql报错
- 【BZOJ2527】【POI2011】Meteors [整体二分]
热门文章
- 20171104xlVBA制作联合成绩条
- 基于windows使用fabric将gitlab的文件远程同步到服务器(本地)
- 小程序点击跳转外部链接 微信小程序提示:不支持打开非业务域名怎么办 使用web-view 配置业务域名
- python-day76--django-Form组件
- zend framwork项目基本操作
- (待解决,效率低下)47. Permutations II C++回溯法
- MySql(九)索引
- HTML标签(二)
- suffix array后缀数组
- 如何仅用递归函数和栈操作逆序一个栈——你要先用stack实现,再去改成递归——需要对递归理解很深刻才能写出来