D. Same GCDs

题目链接:D. Same GCDs

time limit per test:2 seconds memory limit per test:256 megabytes inputstandard input outputstandard 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≤50) — the number of test cases. Next T lines contain test cases — one per line. Each line contains two integers a and m (1≤a<m≤1010). Output Print T integers — one per test case. For each test case print the number of appropriate x-s. input

3
4 9
5 10
42 9999999967

output

6
1
9999999966

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

题目大意

给你两个数 a,m。从[a,a+m)中取出任意一个数x,使得gcd(x,m)=gcd(a,m)成立,问你这样的的x的个数一共有几个。

解题思路

我们设 p=gcd(a,m); 则p=gcd(x,m);然后同时除以p得1=gcd(x/p,m/p);这时候我们发现其实要求的的也就是[a/p,a/p+m/p)中与m/p互质的数有几个。同时减去a/p的,也就是[1,m/p)中于m/p互质的的个数,直接用欧拉函数就可以了;

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
    int t;
    ll a,m;
    cin>>t;
    while(t--)
    {
        cin>>a>>m;
        ll p=__gcd(a,m);
        ll ans=m/p;
        ll q=ans;
        //欧拉函数
        for(ll i=2;i*i<=q;i++)
        {
            if(q%i==0) ans=ans-ans/i;
            while(q%i==0) q/=i;
        }
        if(q!=1) ans-=ans/q;
        cout<<ans<<"\n";
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 牛牛的Link Power II

    时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K 64bit IO Format: %lld 题目描述 牛...

    某些人
  • HPU第一次积分赛 E.Max Gcd

    提示 样例一:删除第四个元素后,2,4,8的最大公因子为2。 样例二:无论删除哪一个,最大公因子都为1。

    某些人
  • C. NEKO's Maze Game

    time limit per test:1.5 seconds memory limit per test:256 megabytes inputstandar...

    某些人
  • AI 在材料制造业的进展与应用

    聊起 AI,画面都充斥着机械语言:精密高级的芯片,光怪陆离的智能产业……你眼中的 AI 有什么样的能力?能给传统行业带来哪些变革与发展?基于此,云加社区联手知乎...

    云加社区
  • Web.Config和Sql Server2005连接字符串总结

     SQL Native Client ODBC Driver 标准安全连接 

    阳光岛主
  • R语言泊松Poisson回归模型分析案例

    这个问题涉及马蹄蟹研究的数据。研究中的每只雌性马蹄蟹都有一只雄性螃蟹贴在她的巢穴中。这项研究调查了影响雌蟹是否有其他男性居住在她附近的因素。被认为影响这一点的解...

    拓端
  • HenCoder Android UI 部分 2-2 全新定义 View 的尺寸

    这期是 HenCoder 布局部分的最后一期:重写 onMeasure() 和 onLayout() 来定制 Layout 的内部布局。

    扔物线
  • NumPy 官方快速入门教程(翻译)

    1、本文是NumPy官方网站(http://www.numpy.org/)的快速入门教程(Quickstart tutorial)的完整翻译版本,原文地址是ht...

    马哥Python
  • SystemVerilog中多态与虚方法

    在验证过程中,往测试平台中添加新的测试激励很正常的事,这样的话就需要对原来的测试平台进行改进,有的时候需要修改原来的代码甚至可能修改一些数据结构,这个过程中可能...

    数字IC小站
  • MySQL主从库--同步异常

    其实就是主要看 Slave_IO_Running 和 Slave_SQL_Running 两个线程的状态。

    lpe234

扫码关注云+社区

领取腾讯云代金券