codeforces-1295D(欧拉函数)
发布日期:2022-03-30 18:18:16 浏览次数:59 分类:博客文章

本文共 1686 字,大约阅读时间需要 5 分钟。

Same GCDs

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given two integers a and m. Calculate the number of integers x such that 0≤x<m and gcd(a,m)=gcd(a+x,m).

Note: gcd(a,b) is the greatest common divisor of a and b.

Input

The first line contains the single integer T (1≤T≤501≤T≤50) — the number of test cases.

Next T lines contain test cases — one per line. Each line contains two integers a and mm (1≤a<m≤10101≤a<m≤1010).

Output

Print T integers — one per test case. For each test case print the number of appropriate x-s.

Example

input

Copy

34 95 1042 9999999967

output

Copy

619999999966

Note

In the first test case appropriate x-s are [0,1,3,4,6,7][0,1,3,4,6,7].

In the second test case the only appropriate x is 00.

题意:给定a和m,求满足gcd(a,m) = gcd(a+x,m)的x数量

题解:首先引出一个原理:gcd(a,b) = gcd(a-b,b)。由此我们可以得到当a+x>=m时,gcd(a+x,m)=gcd(a+x-m,m)。令x' = (a+x)%m,我们可以得知最多有m个不同的x',也就是说x\(\in\)[0,m-1]。问题也就转换成了gcd(a,m) = gcd(x',m)。下面我们令gcd(a,m) = y,令a = ya',m = ym',gcd(a,m) = gcd(ya',ym') = y*gcd(a',m'),可得a'与m'互质,再令x' = yx'',同上,也就是x''与m'互质,同时因为gcd(0,m') = m'>1,得出x''\(\in\)[1,m'-1],根据这个定义,我们可以明白该题的目的就是求出m'内所有与m'互质的数,即m'的欧拉函数

如何求m'的欧拉函数,\(\varphi\)(m') = m'\(\prod_{i=1}^l{(1-{1\over{p_i}})}\),m'直接利用gcd(a,m)即可求出

代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();ll gcd(ll a,ll b){ if(a
1) rea = rea-rea/a; return rea;}int main(){ Test{ ll a,m; cin>>a>>m; cout<

转载地址:https://www.cnblogs.com/cloudplankroader/p/12256412.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:codeforces-1343E(贪心+BFS)
下一篇:2020牛客寒假算法基础训练营1

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2024年03月05日 13时52分47秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

python问题描述怎么写_python写文件有时候写不进去怎么办 2019-04-21
qpython3安装lxml_在python的lxml中使用xml目录? 2019-04-21
java 幂取模_快速幂取模算法 2019-04-21
java build path jre_java-如何在安装了jre 7后为Jre 6设置路径? 2019-04-21
java上传下载源码_javaweb简单实现文件上传与下载源代码 2019-04-21
java socket udp 广播_1.Java 的屏幕广播(基于UDP),2.多线程下载器 2019-04-21
java控制热敏打印机的例子.rar_stm32控制热敏打印机 2019-04-21
java clone equals_(原)java中对象复制、==、equals 2019-04-21
java滚动字幕实训报告_Java实习报告 (7000字).doc 2019-04-21
php7 memcached.exe,PHP7 下安装 memcache 和 memcached 扩展 2019-04-21
计算机二级java技巧,计算机二级报java难考吗 2019-04-21
php foreach 数据库,php – 使用foreach将数据库检索的数据排列在HTML表中 2019-04-21
拉格朗日matlab编程例题,Matlab习题讲解.doc 2019-04-21
case是不是php语言关键字,PHP语言 switch 的一个注意点 2019-04-21
linux php mkdir失败,linux – mkdir错误:参数无效 2019-04-21
config.php渗透,phpMyAdmin 渗透利用总结 2019-04-21
java list 合并 重复的数据_Java ArrayList合并并删除重复数据3种方法 2019-04-21
android volley 上传图片 和参数,android - 使用android中的volley将图像上传到multipart中的服务器 - 堆栈内存溢出... 2019-04-21
android开发的取消清空按钮,Android开发实现带清空按钮的EditText示例 2019-04-21
android gp服务,ArcGIS Runtime SDK for Android开发之调用GP服务(异步调用) 2019-04-21