学步园

http://acm.fzu.edu.cn/problem.php?pid=1017

题意：

给你一个K，要你求一个n, k使得k个n组成的数正好能被K整除，要求首先考虑最小的n，然后考虑最短的k。

思路：

这个题和HDU_2462相似。首先我们可以这样考虑，对于一个由k个n组成的数字，我们不能直接去枚举n和k，那样显然会超时（因为有可能存在不存在n和k的情况），这样我们就设法去把这样的n，k表示成另外一种形式，这样是一定能表示的，因为n，k就可以唯一确定一个数，nn...nn = (99..99) / 9 * n = (10^k
- 1) /9*n ，化简到这里我们就可以直接求了，下面就是过程的推导：
(10^k - 1 ) / 9 * n = 0( mod K )  ---->   (10^k - 1)*n = 0(  mod (9*K) )  ，为了设法将n从左边除掉，我们可以这样化简 ------->

(10^k - 1) = 0 ( mod ( 9*K/gcd(9*K , n) ) ) ， 依据是 ac = bc( mod p ) 化简成a = b ( mod p ) 的条件是 gcd( c , p ) = 0。

到了这里之后，基本的思路就出来了，我们另 p = 9 * K /  gcd( 9*K , n ) ， 上式就变成了：(10^k - 1) = 0 ( mod p ) ---->10^k = 1( mod p )

到这里之后，学过欧拉定理的同学一定就可以看出来了，a^phi(p) = 1 ( mod p ) 当gcd(a, p) = 1 时成立。 这样我们就可以先判断gcd(10 , p )是否等于1 ，如果gcd(10 , p) != 1  ，那么方程一定无解；否则phi(p) 一定是方程的一个解，但是并不一定是最小的解，所以我们还要将p分解质因数然后再判断每个约数是否满足条件即可。

还有一个没有证明的问题就是10^k = 1 ( mod p )当gcd(10 , p)!=1时无解，这个结论可以这样来证明：我们令x = 10 ^ (k-1) ， 则上式就可以变成：10*x = 1 ( mod p )，如果解出了x，那么k也就解出来了，上述那个方程有解的条件就是 gcd(10 , p ) == 1 ， 所以得证。 

代码：

#include <stdio.h>
#include <string.h>

typedef long long LL ;
int K ;
const int PP = 110  ;
int prime[PP] , cnt ;
bool is_p[PP] ;
int fac[20] , num[20] , fnum ;
int ans , p ;

void make_prime(){
    for(int i=1;i<PP;i++)   is_p[i] = 1 ;
    cnt = 0 ;
    for(int i=2;i<PP;i++){
        if( is_p[i] ){
            prime[ cnt++ ] = i ;
            for(int j=2;j*i<PP;j++) is_p[i*j] = 0 ;
        }
    }
}
int gcd(int a, int b){
    while( b ){
        int c = a ;
        a = b ;
        b = c % b ;
    }
    return a ;
}
void get_fac(int n){
    fnum = 0 ;
    for(int i=0;i<cnt && prime[i]*prime[i]<=n;i++){
        if( n%prime[i] == 0 ){
            int c = 0 ;
            while( n%prime[i] == 0){
                c ++ ; n/=prime[i] ;
            }
            fac[ fnum ] = prime[i] ; num[ fnum++ ] = c ;
        }
    }
    if( n > 1 ) fac[ fnum ] = n , num[ fnum++ ] = 1 ;
}

int pmod(int a, int b, int p){
    int res = 1 % p , add = a % p  ;
    while( b ){
        if( b&1 )   res = res * add % p ;
        add = add * add % p ;
        b >>= 1 ;
    }
    return res ;
}

void dfs(int pos , int res ){
    if( pos == fnum ){
        if( pmod(10 , res , p) == 1 ) {
            ans = ans < res ? ans : res  ;
        }
        return ;
    }
    dfs( pos+1 , res)  ;
    int rr = res ;
    for(int i=1;i<=num[ pos ] ;i++){
        rr = rr * fac[ pos ] ;
        dfs(pos+1 , rr) ;
    }
}
int get_phi(int n){
    int res = n ;
    for(int i=0;i<cnt && prime[i]*prime[i]<=n ;i++){
        if( n%prime[i] == 0 ){
            res = res / prime[i] * ( prime[i] - 1 ) ;
            while( n%prime[i] == 0 )    n /= prime[i] ;
        }
    }
    if( n > 1 ) res = res / n * (n - 1) ;
    return res ;
}

int check( int n ){
    p = 9 * K / gcd( 9*K , n ) ;
  //  p = K / gcd(9*K ,  n) * 9 ;
    if( gcd(10,  p) != 1)   return -1 ;
    int ph = get_phi( p ) ;
    get_fac( ph ) ;
    ans = ph  ;
    dfs(0 , 1) ;
    return ans ;
}

int main(){
    make_prime() ;
    while( scanf("%d",&K) == 1 ){
        bool ok = 0 ;
        for(int i=1;i<=9;i++){
            int res = check( i ) ;
            if( res == -1 ) continue ;
            ok = 1 ;
            printf("%d %d\n",i , res);    break ;
        }
        if( !ok )   printf("-1\n");
    }
    return 0 ;
}