Codeforces Round #483 (Div. 2) C. Finite or not?

时间:2023-02-06 13:12:47
C. Finite or not?
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

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.

Input

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.

Output

For each question, in a separate line, print Finite if the fraction is finite and Infinite otherwise.

Examples
input
Copy
2
6 12 10
4 3 10
output
Copy
Finite
Infinite
input
Copy
4
1 1 2
9 36 2
4 12 3
3 5 4
output
Copy
Finite
Finite
Finite
Infinite
Note

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

这题,看这个分数在b进制下是否为无限循环小数。

一个分数是否为无限循环小数取决于分母。

于是想到这题一定是考虑 分母q 和 进制b 的关系,

于是就是想办法  把分母化为1就不是无限循环小数

temp1 = gcd(q, b);
if (temp1 == 1) break;
while(q % temp1== 0) {
q /= temp1;
}
while一定要加 不然会超时。
 #include<bits/stdc++.h>

 using namespace std;
const int maxn = 3e5 + ;
typedef long long LL;
LL gcd(LL a, LL b ) {
if (b == ) return a;
return gcd(b, a % b);
}
int main() {
int n;
LL p, q, b;
scanf("%d", &n);
while(n--) {
scanf("%lld%lld%lld", &p, &q, &b);
LL g = gcd(p, q);
p = p / g, q = q / g;
LL temp = p / q;
p = p - temp * q;
if (!p) {
printf("Finite\n");
continue;
}
LL temp1;
while() {
temp1 = gcd(q, b);
if (temp1 == ) break;
while(q % temp1== ) {
q /= temp1;
}
}
if (q == ) printf("Finite\n");
else printf("Infinite\n");
}
return ;
}

Codeforces Round #483 (Div. 2) C. Finite or not?的更多相关文章

  1. 【数论】Codeforces Round &num;483 &lpar;Div&period; 2&rpar; &lbrack;Thanks&comma; Botan Investments and Victor Shaburov&excl;&rsqb; C&period; Finite or not&quest;

    题意:给你一个分数,问你在b进制下能否化成有限小数. 条件:p/q假如已是既约分数,那么如果q的质因数分解集合是b的子集,就可以化成有限小数,否则不能. 参见代码:反复从q中除去b和q的公因子部分,并 ...

  2. 【Codeforces Round &num;483 &lpar;Div&period; 2&rpar; C】Finite or not&quest;

    [链接] 我是链接,点我呀:) [题意] 在这里输入题意 [题解] 有个性质. 如果p/q是分数的最简形式. 那么p/q能化成有限小数. 当且仅当q的质因数分解形式中只有质因子2和5 (且不能出现其他 ...

  3. Codeforces Round &num;483 &lpar;Div&period; 2&rpar;C题

    C. Finite or not? time limit per test 1 second memory limit per test 256 megabytes input standard in ...

  4. Codeforces Round &num;483 &lpar;Div&period; 2&rpar; &lbrack;Thanks&comma; Botan Investments and Victor Shaburov&excl;&rsqb;

    题目链接:http://codeforces.com/contest/984 A. Game time limit per test:2 seconds memory limit per test:5 ...

  5. Codeforces Round &num;483 &lpar;Div&period; 2&rpar;

    题目链接: https://cn.vjudge.net/contest/229761 A题: n个数字,两个人轮流去数字,直到剩下最后一个数字为止,第一个人希望剩下的数字最小,第二个人希望数字最大,最 ...

  6. Codeforces Round &num;483 Div&period; 1

    A:首先将p和q约分.容易发现相当于要求存在k满足bk mod q=0,也即b包含q的所有质因子.当然不能直接分解质因数,考虑每次给q除掉gcd(b,q),若能将q除至1则说明合法.但这个辣鸡题卡常, ...

  7. Codeforces Round &num;483 &lpar;Div&period; 2&rpar;题解

    A. Game time limit per test 2 seconds memory limit per test 256 megabytes input standard input outpu ...

  8. Codeforces Round &num;483 &lpar;Div&period; 2&rpar; B题

    B. Minesweeper time limit per test 1 second memory limit per test 256 megabytes input standard input ...

  9. Codeforces Round &num;483 &lpar;Div&period; 1&rpar; 简要题解

    来自FallDream的博客,未经允许,请勿转载,谢谢. 为了证明一下我又来更新了,写一篇简要的题解吧. 这场比赛好像有点神奇,E题莫名是道原题,导致有很多选手直接过掉了(Claris 表演24s过题 ...

随机推荐

  1. HTML5分节元素和语义元素

    <base> <base> 元素为文档中的所有链接指定基地址.如果URL中含有协议名或"//"则会忽略 <base> 指定的基地址. <! ...

  2. Mac 下用IDEA时maven,ant打包 (mr 入库hbase)

    现在非常喜欢IDEA,之前在mac 上用的eclipse 经常出现无缘无故的错误.所以转为IDEA.  不过新工具需要学习成本,手头上的项目就遇到了很多问题,现列举如下: 背景描述 在hadoop 开 ...

  3. Could not launch &quot&semi;app&lowbar;name&quot&semi;

    真机测试 不报错 编译通过后 Xcode总出这个错 process launch faild:NotFound-------解决办法 :重启设备

  4. FFMPEG高级编程第一篇:环境搭建及编译

    前段时间在翻看电脑里面资料时,发现了以前做的在嵌入式硬件上面运行以ffmepg为基础,以嵌入式硬件解码的多媒体播放工作,发现都快忘记完了.今日得闲整理温习了一下ffmpeg在嵌入式上的运用,这里给大家 ...

  5. 智能的API、云服务和SOA测试解决方案——Parasoft SOAtest

    依赖Parasoft测试解决方案的机构,不仅有小企业,*机构,还有世界500强集团.Parasoft公司推出的Parasoft SOAtest,提供了API.云服务和SOA最全面的测试解决方案.此次 ...

  6. 你不知道的getComputedStyle

    你不知道的getComputedStyle jQuery的css()的底层实现就用到了getComputedStyle这个方法,也许我们用到的很少,但是不得不说这时一个非常强大的函数,下面让我们一探究 ...

  7. 201521123110 《Java程序设计》第4周学习总结

    1. 本周学习总结 1.1 尝试使用思维导图总结有关继承的知识点. 1.2 使用常规方法总结其他上课内容. private不对用户公开进行修改,public用户可以进行修改.代码可以进行继承,即子类继 ...

  8. 芝麻HTTP:Scrapyd的安装

    Scrapyd是一个用于部署和运行Scrapy项目的工具,有了它,你可以将写好的Scrapy项目上传到云主机并通过API来控制它的运行. 既然是Scrapy项目部署,基本上都使用Linux主机,所以本 ...

  9. wx :swipertab切换

    <view> <view class="navbar"> <block wx:for="{{body}}" wx:key=&quo ...

  10. Agent XPs disable

    问题 有一天,我们发现SQL Server代理程序在SSMS“SQL Server代理程序(Agent XPs已禁用)”中为我们的SQL Server实例之一停止了以下消息,但该服务正在根据服务控制台 ...