正文

zju-1489-2^x mod n = 12005-10-06 19:30:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/ddtme/5786.html

分享到:


#include<stdio.h>

int modular(int a,long b,int n)
{
    long d,t ;
    d=1 ;
    t=a ;
    while(b>0)
    {
        if(b%2==1)
        d=d*t%n ;
        b=b/2 ;
        t=t*t%n ;
    }
    if(d==1)
    return 1 ;
    else return 0 ;
}

int main()
{
    long n ;
    long i ;
    while(scanf("%ld",&n)!=EOF)
    {
        if((n%2==0)||(n==1))
        {
            printf("2^? mod %ld = 1\n",n);
            continue ;
        }
        for(i=1;;i++)
        if(modular(2,i,n))
        {
            printf("2^%ld mod %ld = 1\n",i,n);
            break ;
        }
        
    }
    return 0 ;
}

/*
#include<iostream>
using namespace std;
int main()
{
    int n,a;
    __int64 k;
    while(cin>>n)
    {
        if(n%2 != 0)
        {
            for(a=1;a<n;a++)
            {
                k = 1;
                k<<=a;
                if(k%n==1)
                    break;
            }
            if(a==n)
                cout<<"2^? mod "<<n<<" = 1"<<endl;
            else
                cout<<"2^"<<a<<" mod "<<n<<" = 1"<<endl;
        }
        else
        {
            cout<<"2^? mod "<<n<<" = 1"<<endl;
        }
    }
    return 0;
}
*/

阅读(5945) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册