hdu2837数论
数论
2023-09-27 14:23:51 时间
http://acm.hdu.edu.cn/showproblem.php?pid=2837
// a^b%p=a^(b%phi(p)+phi(p))%p
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<bitset> #include<iomanip> using namespace std; #define INT long long INT euler( int n) { INT ret=1,i; for (i=2;i*i<=n;i++) if (n%i==0){ n/=i,ret*=i-1; while (n%i==0) n/=i,ret*=i; } if (n>1) ret*=n-1; return ret; } INT Pow( INT a , INT b , INT m ) { INT ans = 1 ; while( b ) { if( b & 1 ) { ans = ans * a % m ; } a *= a ; a %= m ; b >>= 1 ; } return ans % m ; } INT fun2( int a , int b , int m ) { INT ans = 1 ; for( int i = 1 ; i <= b ; ++i ) { ans *= a ; if( ans >= m ) return ans ; } return ans ; } INT fun1( int n , int m ) { INT phi = euler( m ) ; if( n < 10 ) return n ; INT a = fun1( n / 10 , phi ) ; INT b = fun2( n % 10 , a , m ) ; if( b >= m ) { INT ans = Pow( n % 10 , a + phi , m ) ; if( ans == 0 ) ans += m ; return ans ; } return b ; } int main() { int Case , n , m , p ; cin >> Case ; while( Case-- ) { cin >> n >> m ; INT ans = fun1( n , m ) % m ; cout << ans << endl ; } return 0 ; }
相关文章
- HDU4279(2012年天津网络赛---数论分析题)
- 《数学与泛型编程:高效编程的奥秘》一第3章 古希腊的数论
- 【数论】关于质数的几个定理,用 latex 来表示数学公式
- 数论基础代码合集
- HDU1058 Humble Numbers 【数论】
- 2019牛客多校第三场D BigInteger——基础数论
- 多项式乘法(FFT)模板 && 快速数论变换(NTT)
- 初等数论初步——算数基本定理
- 每个程序员都应该知道的基础数论
- 【luogu P1495】【模板】中国剩余定理(CRT)/曹冲养猪(数论)
- 【nowcoder 225876】与巨(数论)
- 【luogu P5221】Product(数论)
- 【luogu P4777】【模板】扩展中国剩余定理(EXCRT)(数论)
- [数论] 快速傅里叶变换FFT