数据叠加超过取值范围。 - 编程论坛

#2

rjsp2018-09-30 13:52

不要计算完毕后再模除10^9
而应该在计算的中途就模除10^9，即 (a * b) % c == (a%c * b%c) % c。
快速幂就行了

BTW：

我的思路就是直接(n^2+1)*n^2/2

写错了吧，我怎么觉得应该是 (2^n+1) * 2^n / 2

#3

rjsp2018-09-30 14:13

你没贴原始链接，所以不解处我是瞎猜的，以下代码仅供参考

程序代码：

#include <stdio.h>

// 计算 (a^b)%1000000007
unsigned quickpow( unsigned a, unsigned b )
{
    unsigned result = 1;
    for( unsigned t=a; b; b/=2 )
    {
        if( b%2 == 1 )
            result = (result*1ull*t)%1000000007;
        t = (t*1ull*t)%1000000007;
    }
    return result;
}

int main( void )
{
    unsigned n;
    scanf( "%u", &n );

    // 计算 (2^n+1) * 2^n / 2
    unsigned t = quickpow( 2, n-1 );
    unsigned r = unsigned r = ((2*t+1ull)*t)/1000000007;
    printf( "%u\n", r );
}

[此贴子已经被作者于2018-9-30 14:22编辑过]

#4

Jeff_2018-09-30 17:10

回复 3楼 rjsp

#include<iostream>
#include<math.h>
using namespace std;
int main()
{
    long int  n, s, t;
    cin >> n;

    s = pow( 2 ,  (long double) n ) * ( 1 + pow( 2, (long  double) n )) / 2 ;
    t = ( pow( (long double) 10, (long double) 9 ) + 7 );
    s = (unsigned)s % (unsigned)t;
    cout << s << endl;
    return 0;
}
这是我第一次写的，发现超过范围，我就想着在1+2+3+....一旦超过范围就取模，但是循环了太多超时了
#include<iostream>
#include<math.h>
using namespace std;

int main()
{
    int  num=0;
    double n;
    const double ou=9;
    cin >> n;
    for(int i=0; num<(pow(2,n)+1)*pow(2,n)/2 ; i++)
    {
        if(num>pow(2,ou)+7)
         num=num%(num<pow(2,ou)+7);
        num +=i;

    }
    cout << num << endl;

    return 0;
}

现在问题是a*b%c变成了（a%c*b%c）但是a超过了范围。就像我第一次写的  2^n，n输入100，n>63 longlong的取值就超过了，然后被取了近似，即使取模得到的也不是准确的数据而是被取近似后的数据。

@ ——！