经典蓝桥题目-------欧拉函数的应用

输入样例：

3
4 9
5 10
42 9999999967

输出样例：

6
1
9999999966

分析：

设  gcd(a,m) = d,则 d|a,d|m

而  gcd(a,m) = gcd(a+x,m) 则有 d|x

根据题目有 0<=x<m

同样的有 0<= x' < m'     (x',m'是同时除以d的值)

于是我们发现只要求m'的欧拉函数即可

不会欧拉函数的可以看我这篇博客，写的很详细

欧拉函数的定义与应用

代码演示：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;typedef long long LL;// 求最大公约数
LL gcd(LL a,LL b)
{return b?gcd(b,a%b):a;
}// 求欧啦函数
LL calc_primes(LL n)
{LL res = n;for(LL i=2;i<=n/i;i++){if(n%i==0){res = res/i*(i-1);while(n%i==0) n /= i;}}if(n>1) res = res/n*(n-1);return res;
}int main(void)
{int t;cin >> t;while(t--){LL l,r;cin >> l >> r;LL d = gcd(l,r);cout << calc_primes(r/d) << endl;}return 0;
}

感谢查看！