首页 > 代码库 > HDU 3307 Description has only two Sentences

HDU 3307 Description has only two Sentences

2024-07-25 09:43:08   220人阅读

 

Description has only two Sentences

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 886    Accepted Submission(s): 265


Problem Description
an = X*an-1 + Y and Y mod (X-1) = 0.
Your task is to calculate the smallest positive integer k that ak mod a0 = 0.
 

 

Input
Each line will contain only three integers X, Y, a0 ( 1 < X < 231, 0 <= Y < 263, 0 < a0 < 231).
 

 

Output
For each case, output the answer in one line, if there is no such k, output "Impossible!".
 

 

Sample Input
2 0 9
 

 

Sample Output
1
 

 

Author
WhereIsHeroFrom
 

 

Source
HDOJ Monthly Contest – 2010.02.06

 

题目要求求一个  Ai =  XAi + Y and Y %(x-1) == 0 的  Ak % A0 == 0 的最小 k

然后开始推公式

可得   A n  = X^n *  A0  + (  x^(n-1) + x *(n-2) + ...... + x + 1 ) * Y

显然  X^n * A0 必然整除 A0 可以忽略  ， 然后  后项是一个等比数列 。

然后处理一下得到想要求的就是   （ X ^ k -1 ）/ ( x - 1 ) * Y    %  A0  ==  0 的最小k

转换一下    。。   设系数为  e  ,

就是    e * A0  = ( X^k - 1 ) / (X - 1 )  * Y ;

          e * ( A0 / gcd(A0 , Y / (X - 1 ) ) ) =  X^k - 1 。 

          设  m  = ( A0 / gcd(A0 , Y / (X - 1 ) ) )  . 

          得到   X^k == 1 ( mod m )

 

对m求一次单个欧拉 ， 然后判一下 。 

impossible 那里要特判一下X与m是否互质  ，若不互质，则X^k%m必定是gcd(m,X)的倍数  

 

#include <algorithm>#include <cstring>#include <cstdio>#include <queue>#include <iostream>#include <vector>#include <string>#include <map>using namespace std;typedef long long ll;const int N = 100010;ll mod , tot ;ll gcd ( ll a , ll b ) { return b == 0 ? a : gcd( b ,a % b ); }ll eular ( ll n ){    ll sum = n ;    for( ll i = 2 ; i* i <= n ; ++i ){        if(  n % i == 0 ){            sum = sum / i *( i -1 );            while( n % i == 0 ) n /= i ;        }    }    if( n > 1 ) sum = sum / n * ( n -1 ) ;    return sum;}ll quick_mod( ll a , ll b ){    ll res = 1 ;    while( b ){        if( b & 1 ) res =  res * a % mod ;        a = a * a % mod;        b >>= 1 ;    }    return res ;}ll e[N] ;void get_factor( ll n ){    for( ll i = 2 ; i * i <= n ; ++i ){        if( n % i == 0 ){            e[tot++] = i ;            if( n / i != i ) e[tot++ ] = n / i ;        }    }}int  main(){    ios::sync_with_stdio(0);    #ifdef LOCAL        freopen("in.txt","r",stdin);    #endif    ll a0 , x , y ;    while( cin >> x >> y >> a0 ){        tot = 0 ;        if( !y ) { cout << ‘1‘ <<endl ; continue ;}        ll m = a0 / gcd( y / ( x - 1 )  ,a0 ) ;        if( gcd(m ,x) != 1 ) { cout << "Impossible!" << endl ; continue ; }        ll phi = eular(m) ;        get_factor(phi) ;        sort(e , e + tot ) ;        mod = m ;        for( int i = 0 ; i < tot ; ++i ){            if( quick_mod( x,e[i]) == 1 ){ cout <<e[i] << endl ; break ; }        }    }}

 

HDU 3307 Description has only two Sentences


联系
我们