时间戳

首页 > 解决方案 > 为什么答案是垃圾值？

c++ - 为什么答案是垃圾值？

问题描述

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define M 1000000007
using namespace std;
int main()
{
    fastio;
    int t;
    cin >> t;
    while(t--)
    {
        long n,a;
        cin >> n >> a;
        ll ans=0,x=a,y;
        for(long i=1;i<=n;i++)
        {
            y=pow(x,(2*i-1));
            ans=(ans%M+y%M)%M;
            x=(x*y)%M;
        }
        cout << ans << "\n";
    }
}

鉴于此输入

1
4 10

我得到了一个垃圾值。这是为什么？

但是，对于此输入：

1
3 2

我得到的答案似乎完全没问题。

标签： c++

解决方案

我不确定正确的输出应该是什么，但看起来你有溢出。在pow函数中，您计算​​整个结果然后取模。由于结果可能非常大，甚至无法放入long long，因此在获取 mod 之前它会溢出，从而得到错误的答案。一个简单的解决方案是实现一个Pow函数，该函数在 mod 倍增时采用该函数。该代码还有一些其他问题，例如导入bits/stdc++.h,和.... 但这无关紧要。但我想这段代码是为了解决一些问题。using namespace stdllM

有问题的代码可能已解决：

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define M 1000000007
using namespace std;

long long Pow(int n, int p)
{
    if (p == 0) return 1;

    auto res = Pow(n, p / 2);

    res *= res;
    res %= M;

    if (p % 2 == 1)
        res *= n, res %= M;

    return res;
}

int main()
{
    fastio;
    int t;
    cin >> t;
    while(t--)
    {
        long n,a;
        cin >> n >> a;
        ll ans=0,x=a,y;
        for(long i=1;i<=n;i++)
        {
            y=Pow(x,(2*i-1));
            ans=(ans%M+y%M)%M;
            x=(x*y)%M;
        }
        cout << ans << "\n";
    }
}

输入：

1 4 10

输出：

707919736

推荐阅读