首页 > ACM题库 > HDU-杭电 > HDU 1395 2^x mod n = 1-最小生成树-[解题报告] C++
2013
12-09

HDU 1395 2^x mod n = 1-最小生成树-[解题报告] C++

2^x mod n = 1

问题描述 :

Give a number n, find the minimum x(x>0) that satisfies 2^x mod n = 1.

输入:

One positive integer on each line, the value of n.

输出:

If the minimum x exists, print a line with 2^x mod n = 1.

Print 2^? mod n = 1 otherwise.

You should replace x and n with specific numbers.

样例输入:

2
5

样例输出:

2^? mod 2 = 1
2^4 mod 5 = 1

地址:http://acm.hdu.edu.cn/showproblem.php?pid=1395

题意:给出n,求满足2^x mod n = 1的最小的x。

mark:数论题,其实就是求a模m的阶。打素数表敲错变量,1wa。可以水过,但是最好需要知道以下知识。

1. 若gcd(a,m)==1,一定存在一个正整数d<m使得a^d == 1 mod m(欧拉定理)。

2. 满足条件的最小正整数d记为ord_m(a),叫做a模m的阶。

3. 若对于一个正整数a满足(1)gcd(a,m)==1;(2)ord_m(a)==φ(m)(φ(m)表示m的欧拉函数);则a叫做m的一个原根。

4. 若gcd(a,m)==1且a^d == 1 mod n,则φ(m)一定是d的倍数。因此,φ(m)一定是ord_m(a)的倍数。

5. 模m有原根的充要条件是m = 1,2,4,p^n, 2p^n,其中p是奇素数,n是任意正整数(只是有原根,并不是说gcd(a,m)==1则a一定是m的原根)。

6. 当模m有原根时,它有φ(φ(m))个原根。

7. 除了直接运算以外,至今还没有一个办法可以找到模特定m时的原根,但假如已知模m有一个原根,则可找出它其他的原根。

代码:

# include <stdio.h>
# include <math.h>



int IsPrime[5010] ;


void init()
{
    int i, j ;
    for(i = 0 ; i <= 5000 ; i++) IsPrime[i] = 1 ;
    for (i = 2 ; i<= 71 ; i++) if (IsPrime[i])
        for (j = i*i ; j <= 5000 ; j+=i) IsPrime[j] = 0 ;
}


int EulerPhi(int num)
{
    int phi = num, sq = sqrt(num) + 1, p ;
    for (p = 2 ; p <= sq ; p++) if (num%p==0)
    {
        phi = phi/p * (p-1) ;
        while (num%p==0) num /= p ;
    }
    if (num > 1) phi = phi / num * (num-1) ;
    return phi ;
}


int qpow(int a, int b, int mod)
{
    int rtn = 1, buff = a ;
    while (b)
    {
        if (b&1) rtn = (rtn*buff) % mod ;
        buff = (buff*buff)%mod ;
        b >>= 1 ;
    }
    return rtn ;
}


int main ()
{
    int ans, phi, n, i ;
    init() ;
    while (~scanf ("%d", &n))
    {
        if (n == 1 || ((n&1) == 0))
            printf ("2^? mod %d = 1\n", n) ;
        else{
            phi = EulerPhi(n) ;
            if (IsPrime[phi]) ans = phi ;
            else{
                for (i = 1 ; i <= phi ; i++) if (phi%i == 0)
                {
                    if (qpow(2,i,n) == 1){
                        ans = i ;
                        break ;
                    }
                }
            }
            printf ("2^%d mod %d = 1\n", ans, n) ;
        }
    }
    return 0 ;
}

解题报告转自:http://www.cnblogs.com/lzsz1212/archive/2012/02/15/2352047.html


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.