模运算怎么算 - 编程论坛

#2

zhuanjia02012-12-01 14:14

很简单的一道题啊！

程序代码：

int n;
cout<<"输入正整数n (1 <= n <= 2*10^8):"<<endl;
cin>>n;
cout<<"结果:"<<(2^n)%100000007<<endl;//输出2的n次方除以100000007取余（就是模100000007）的结果

#3

azzbcc2012-12-01 14:18

程序代码：

#include <stdio.h>
#define N 100000007
int main()
{
    int M;
    int s;
    while ((scanf("%d", &M)) != EOF)
    {
        s = 1;
        do {
            s *= 2;
            if (s > N)
            {
                s %= N;
            }
        } while(--M);
        printf("%d\n", s);
    }
}

#4

lin3890641812012-12-01 16:35

回复 3楼 azzbcc

试多几组数就出错了

#5

azzbcc2012-12-01 17:32

莫非楼主用的是TC，把int改为long就行

#6

lin3890641812012-12-01 18:35

回复 5楼 azzbcc

是VC。。但这个算到27次方的时候就错了。。。

#7

azzbcc2012-12-01 19:50

我不会发图，结果不是33，554，432么？对的呀！

#8

lin3890641812012-12-01 22:39

回复 7楼 azzbcc

我用你这个验算了一下 26次方是67108864 可27次方是34217721

#9

azzbcc2012-12-01 23:10

肯定当时抄错了，不过按照楼主的
26 ：67108864 % 100000007 = 67108864

27 ：67108864 * 2 % 100000007 = 134217728 % 100000007 = 34217721
对的啊！

#10

lin3890641812012-12-01 23:16

回复 9楼 azzbcc

Time Limit Exceeded超时了

#11

lin3890641812012-12-01 23:18

回复 9楼 azzbcc

貌似要用到快速幂吧

#12

azzbcc2012-12-01 23:29

==我想想

#13

lin3890641812012-12-01 23:36

回复 12楼 azzbcc

就这性质
(a + b) % m = (a % m + b % m) % m;
(a * b) % m = ((a % m) * (b % m)) % m;

#14

azzbcc2012-12-01 23:50

程序代码：

#include <stdio.h>
#include <math.h>
#define N 100000007
int main()
{
    long M;
    __int64 s;
    __int64 temp = (__int64)pow(2, 62) % N;

    while ((scanf("%ld", &M)) != EOF)
    {
        s = 1;
        while(M > 62)
        {
            M -= 62;
            s *= temp;
            if (s > N)
                s %= N;
        }
        s = s * (__int64)pow(2, M) % N;
        printf("%I64d\n", s);
    }
    return 0;
}

#15

lin3890641812012-12-02 00:18

回复 14楼 azzbcc

唉。。上交还是现实WRONG ANSWERS

#16

azzbcc2012-12-02 01:01

找了半天抽屉数，大于200,000了，这道题要我命啊！！！

咳咳，会不会不识别__int64。唉，算了，当我没说过。。。

#17

lin3890641812012-12-02 08:04

回复 16楼 azzbcc

呵。。。也要了我的命啊。。。不过已经很感谢你了

#18

lin3890641812012-12-02 14:13

回复 14楼 azzbcc

不用VC交就过了

#19

azzbcc2012-12-02 18:53

程序代码：

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

#define  Mount     10
#define  Pow_Size  50
#define  N  100000007

int main()
{
    long M, n;
    __int64 s;
    __int64 temp[Mount + 1];

    temp[0] = (__int64)pow(2, Pow_Size) % N;
    for (int i = 1;i <= Mount;i++)
        temp[i] = temp[i - 1] * temp[i - 1] % N;
    //temp[]初始化，将 pow(2,(pow(2, i) * Pow_Size)) % N 存入temp[i]

    while ((scanf("%ld", &M)) != EOF)
    {
        s = 1;    i = Mount;
        n = (long)pow(2, Mount) * Pow_Size;
        while(M > 50)
        {
            if (M < n)
            {
                i--;    n /= 2;
            }
            else
            {
                M -= n;
                s = s * temp[i] % N;
            }
        }
        s = (__int64)pow(2, M) % N * s % N;
        printf("%I64d\n", s);
    }
    return 0;
}

[ 本帖最后由 azzbcc 于 2012-12-2 19:00 编辑 ]

#20

azzbcc2012-12-02 18:55

14楼
s = s * (__int64)pow(2, M) % N;
有错
应该是
s = (__int64)pow(2, M) % N * s % N;

#21

rjsp2012-12-03 09:11

重复发帖，别人当天就回答你了
http://bbs.