欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

数据结构算法(思维+欧拉函数)

程序员文章站 2022-07-09 16:35:16
A Very Easy Math ProblemDescription有一天ZKL遇到一道数学题。给定三个正整数a,b,m,问有多少个整数x满足0≤x

A Very Easy Math Problem

Description
有一天ZKL遇到一道数学题。给定三个正整数a,b,m,问有多少个整数x满足0≤x<m并且gcd(a+b,m)=gcd(b-a+x,m)。但是这对于号称“数学天才”的ZKL来说过于简单了,所以现在她把这道问题抛给了你。

gcd(a,b)代表a和b的最大公约数。

Input
第一行一个整数T代表有T组询问。(1≤T≤10)

接下来T行每行三个整数a,b,m(1≤a≤b≤1e12 , 1≤m≤1e12)。

Output
T行,第i行代表第i组询问中,满足条件的x的数量

Samples
input
3
1 2 3
2 2 9
12 123 1234
output
1
6
616
Author
QIU, Longfeng

思路: 令tmp=gcd(a+b,m),问你有几个x满足gcd(b-a+x,m)==tmp。根据欧几里得算法,gcd(b-a+x,m) == gcd(m,(b-a+x)%m)。此时我们令k=(b-a+x)%m,因为0<=x<m,所以我们可以发现一个x对应一个k,同时k的范围0<=k<m。然后我们就可以将题目转化为0<=k<m,求满足gcd(m,k)==tmp式子k的数量。我们可以发现当k == 0时与k == m时gcd(m,k)都等于m,于是我们可以将k的范围转化成0<k<=m,我们可以得到一下式子,再经过转化,我们可以得到所求即为小于等于(m/tmp)且与(m/tmp)互质的数的数量就是求φ(m/tmp)。
数据结构算法(思维+欧拉函数)

#include<list> #include<string.h> #include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<string> #include<cstring> #include<vector> #include<map> #include<deque> #include<stack> #include<queue> #include<set> #include<iomanip> #include<cstdlib> #include<stdexcept> #include<fstream> #include<iterator> using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e6+10; const int inf = 0x3f3f3f3f; const int Base =131; const ll INF = 1ll << 62; //const double PI = acos(-1); const double eps = 1e-7; const int mod = 1e9+7; #define mem(a,b) memset(a,b,sizeof(a)) #define speed {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); } inline ll gcd(ll a, ll b){ while (b ^= a ^= b ^= a %= b); return a; } ll Euler(ll n) {//求φ(m/tmp) ll res = n; for (ll i = 2; i*i <= n; 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(){ int T; scanf("%d",&T); while(T--){ ll a,b,m; scanf("%lld %lld %lld",&a,&b,&m); ll tmp=gcd(a+b,m); printf("%lld\n",Euler(m/tmp)); } //system("pause"); return 0; } 

本文地址:https://blog.csdn.net/m0_49041421/article/details/107911901

相关标签: 思维 数论