poj3358数论（欧拉定理）

初始状态为分数形式）小数点进制转换原理：n / m ;

n /= 易做图( n , m ) ;

m/= 易做图( n , m ) ;

n = n % m ;

for( i : 0 to .....)

n *= k ;

bit[ i ] = n / m;(保留每一位的数值）

n %= m ;

题意：求n/m的小数点位的循环数列的长度和起始位置；

现在假设起始循环的第i个数为n,记作ni ；那么第j个数n，则是nj；这时循环数列出现，那么循环数列的长度为 L = j - i .

又根据小数点进制的计算原理,那么就有nj = ( ni * 2 ^ L ） % m ；————>2 ^ L % m == 1 % m ;（求t是利用这里求的）

 当　m 　与　２　互质时，根据欧拉定理，则有２^ phi( m ) == 1 %m ，因为２^　０　＝＝　１　，　所以起始点为0 ;也就是题目的１;

当二者不互质时，那么m　％　２　！＝　０ ;

因此对等式进行化简　，两边同时除以２的幂次（使得m与２互质，直到满足欧拉函数的条件），那么就有2^( L - t ) == 1 % ( m / ( 2 ^ t );可知，此时循环数列的起点为　t ，也就是题目的t＋１;

最后我们要求的就是2^ L' = 1 % M' ;由于２^ k == 1 % m ',当k % m == 0 时取得有效值，因此，从小到大枚举phi(m')的因子，可得到最大值

#include<iostream>   
#include<cstdio>   
#include<cstring>   
#include<cmath>   
#include<algorithm>   
#include<bitset>   
#include<iomanip>   
  
using namespace std;  
int t, n, m, 易做图, phi, ans1, ans2;  
int temp, num;  
int fac[1000000];  
   
int 易做图( int a , int b )  
{  
    return b == 0 ? a : 易做图( b , a % b );  
}  
  
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 c )  
{  
    int ans = 1 ;   
    while( b > 0 )  
    {  
        if( b & 1 )  
        {  
            ans = ( long long ) ans * a % c ;  
        }  
        b >>= 1 ;  
        a = ( long long )a * a % c ;  
    }  
    return ans ;  
}   
   
int main()  
{  
    int Case = 1 ;  
    while( scanf( "%d/%d" , &n , &m ) != EOF )  
    {  
        易做图 = 易做图( n , m ) ;  
        n /= 易做图 ;  
        m /= 易做图 ;  
        t = 0 ;  
        while( m % 2 == 0 )  
        {  
            t++ ;  
            m /= 2 ;  
        }  
        ans1 = t + 1 ;  
        phi = euler( m ) ;  
        if( phi == 1 )  
        {  
            ans2 = 1 ;   
        }  
        else  
        {  
            int num = 0 ;  
            for( int i = 1 ; i * i <= phi ; ++i )  
            {  
                if( phi % i == 0 )  
                {  
                    fac[ num++ ] = i ;  
                    fac[ num++ ] = phi / i ;  
                }  
            }  
            sort( fac , fac + num ) ;  
            for( int i = 0 ; i < num ; ++i )  
            {  
                temp = Pow( 2 , fac[ i ] , m ) ;  
                if( temp == 1 )  
                {  
                    ans2 = fac[ i ] ;   
                    break ;  
                }  
            }  
        }  
        printf( "Case #%d: %d,%d\n" , Case++ , ans1 , ans2 ) ;        
    }  
    return 0 ;  
}  

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<iomanip>

using namespace std;
int t, n, m, 易做图, phi, ans1, ans2;
int temp, num;
int fac[1000000];
 
int 易做图( int a , int b )
{
	return b == 0 ? a : 易做图( b , a % b );
}

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 c )
{
	int ans = 1 ; 
	while( b > 0 )
	{
		if( b & 1 )
		{
			ans = ( long long ) ans * a % c ;
		}
		b >>= 1 ;
		a = ( long long )a * a % c ;
	}
	return ans ;
} 
 
int main()
{
	int Case = 1 ;
	while( scanf( "%d/%d" , &n , &m ) != EOF )
	{
		易做图 = 易做图( n , m ) ;
		n /= 易做图 ;
		m /= 易做图 ;
		t = 0 ;
		while( m % 2 == 0 )
		{
			t++ ;
			m /= 2 ;
		}
		ans1 = t + 1 ;
		phi = euler( m ) ;
		if( phi == 1 )
		{
			ans2 = 1 ; 
		}
		else
		{
			int num = 0 ;
			for( int i = 1 ; i * i <= phi ; ++i )
			{
				if( phi % i == 0 )
				{
					fac[ num++ ] = i ;
					fac[ num++ ] = phi / i ;
				}
			}
			sort( fac , fac + num ) ;
			for( int i = 0 ; i < num ; ++i )
			{
				temp = Pow( 2 , fac[ i ] , m ) ;
				if( temp == 1 )
				{
					ans2 = fac[ i ] ; 
					break ;
				}
			}
		}
		printf( "Case #%d: %d,%d\n" , Case++ , ans1 , ans2 ) ;		
	}
	return 0 ;
}

补充：软件开发 , C++ ,

上一个：hdu1711
下一个：hdu 4611