HE Fredo and Maths ( Math, Totient function )
Fredo and Maths | Totient Function & Math Practice Problems | HackerEarth
題意:
T 筆詢問。問 x^x^x^x^x^x... % M,其中有 K 個 x,為多少。
制約:
1 ≤ T ≤ 1e5
1 ≤ M ≤ 1e7
1 ≤ K ≤ 1e18
M < X ≤ 1e8, X is always a prime number
解法:
利用尤拉定理可以知道,x^phi( M ) % M == 1,利用這件事遞迴求解。
因此遞迴的深度不會超過 phi 的數量,使得 phi( phi( phi( ... phi( M ) ... ) = 1。
因為 phi 函數很快收斂,所以 ok ( 吧 )。
不知道為什麼被微卡常數,怒開 avx 優化就過了。
時間 / 空間複雜度:
玄學。
#pragma GCC target ("avx") // ターゲットの変更 sse4, avx, avx2 など #include <bits/stdc++.h> using namespace std; bool np[ ( int ) 1e7 + 1 ]; int phi[ ( int ) 1e7 + 1 ]; int int_pow( int v, int p, int m ) { int res = 1; while( p ) { if( p & 1 ) { res = 1LL * res * v % m; } p >>= 1; v = 1LL * v * v % m; } return res; } int dfs( int x, int k, int m ) { if( m == 1 ) return 0; if( k == 1 ) return x % m; return int_pow( x, dfs( x, k - 1, phi[ m ] ), m ); } signed main() { for( int i = 1; i <= ( int ) 1e7; ++i ) { phi[ i ] = i; } for( int i = 2; i <= ( int ) 1e7; ++i ) { if( np[ i ] ) continue; for( int j = i; j <= ( int ) 1e7; j += i ) { if( j != i ) { np[ j ] = true; } phi[ j ] = phi[ j ] / i * ( i - 1 ); } } int T; scanf( "%d", &T ); for( int ti = 0; ti < T; ++ti ) { int X, M; long long K; scanf( "%d %lld %d", &X, &K, &M ); printf( "%d\n", dfs( X, min( 1LL * M, K ), M ) ); } return 0; }