2 qq 31601743 qq_31601743 于 2016.04.15 19:36 提问

2^x mod n = 1超时怎么解决呀
c++

2^x mod n = 1
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 15197 Accepted Submission(s): 4695

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

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

Output
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.

Sample Input
2
5

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

2个回答

qq_31601743
qq_31601743   2016.04.15 19:37

代码如下,超时
#include
using namespace std;

int main()
{
int n;
int x;
int d;

while(cin >> n)
{
    d= 0;
    if(n%2==0||n==1)
        cout << "2^? mod 2 = 1" << endl;

    else
    {
        x = 1;
        while(1)
        {
            x=x*2;d++;
            if(x%n==1)
            {
                cout << "2^"<<d<< " mod 2 = 1" << endl;
                break; 
            }

        }

    }

}
return 0;

}

CSDNXIAON
CSDNXIAON   2016.04.15 19:42

2^x mod n = 1
2^x mod n = 1
2^x mod n = 1
----------------------同志你好,我是CSDN问答机器人小N,奉组织之命为你提供参考答案,编程尚未成功,同志仍需努力!

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
杭电 1395 2^x mod n = 1 暴力题
一直以为有什么高深的算法,,没想到暴力一下就能过。。这太悲剧了。可以用欧拉定理证明其存在性。欧拉定理是这样的,如果a和m互质且a 2^x mod n = 1 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5974    A
2^x mod n = 1【费马小定理】
2^x mod n = 1 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13617    Accepted Submission(s): 4212 Problem Description Give a nu
数论模板 满足a^x≡1(mod n)的最小正整数
Description 满足a^x≡1(mod n)的最小正整数x称为a模n的阶。 现给出两个正整数,求x。 Input 第一行输入k,表示有k组数据 之后k行每行两个数a,n(2 Output 对于每组输入,用一行输出x的值,若不存在输出-1 Sample Input 22 32 4 Sa
给定一个正整数n,要求找到最小的x(x>0)满足2^x mod n = 1。
输入 输入包含多组测试数据。每行一个正整数,代表n的值。 输出 如果最小的x存在,则输出2^x mod n = 1(注意x和n要用具体的值代替),否则输出2^? mod n = 1。 #include int main() { int n,x,y,; while(scanf("%d",&n)!=EOF) { if(n pri
A^X mod P 山东省赛,打表求解
给一个链接:http://acm.upc.edu.cn/problem.php?id=2219 就是给一个公式,求冪取余。 拿到则这个题的时候,感觉挺简单的,n的范围是10^6,而qmod的复杂度为log2 N=30左右,所以,应该不会TLE吧,可惜还是TLE了。看来1s只能处理10^6的数量级的复杂度了,10^7就会TLE了。 反正我是想不到这种方法了。因为我以为, 时间复杂度已经到达极限
HDU 1573 X问题 中国剩余定理
链接:http://acm.hdu.edu.cn/showproblem.php?pid=1573 题意:求在小于等于N的正整数中有多少个X满足:X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 思路:中国剩余定理的模板题,如果找不到这样的数或者最小的X大于N,输出零。 代
2^n % mod当mod为质数
当n非常大,所以这里要用到费马小定理:a^(p-1)%p == 1%p == 1;//p为素数  所以2^n%m == ( 2^(n%(m-1))*2^(n/(m-1)*(m-1)) )%m == (2^(n%(m-1)))%m * ((2^k)^(m-1))%m == (2^(n%(m-1)))%m;//k=n/(m-1)
HDU1573:X问题(中国剩余定理)
求在小于等于N的正整数中有多少个X满足:X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 &amp;lt; a[i] &amp;lt;= 10)。Input输入数据的第一行为一个正整数T,表示有T组测试数据。每组测试数据的第一行为两个正整数N,M (0 &amp;lt; N &amp;lt;= 1000,000,...
数论 - 用扩展欧几里得解模线性方程ax≡b (mod n) + 生理周期
因为方法本身比较死所以就直接上代码吧。 #include using namespace std; //扩展欧几里得算法 int extended_gcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1; y = 0; return a; } int r = extended_gcd(b, a % b, x, y
hdu 1573: X问题(线性同余方程组求正整数解的个数)
X问题 Problem Description 求在小于等于N的正整数中有多少个X满足:X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0   Input 输入数据的第一行为一个正整数T,表示有T组测试数据。每组测试数据的第一行为两个正整数N,M (0