-1
#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";
    }
}

Given this input

1
4 10

I'm getting a garbage value back. Why is that?

However, for this input:

1
3 2

The answer I'm getting back seems totally fine.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Advait Acharya
  • 1
  • One possible problem: `pow()` uses floating-point math (i.e. it takes `double` arguments and returns a `double` result) rather than `long long` integer math, which means that its results are susceptible to all the usual floating-point roundoff-error problems. You might want to use your own `ipow()` function instead to avoid that complication (see: https://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int ) – Jeremy Friesner Apr 20 '20 at 18:14
  • What garbage are you referring to? Also, read https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h and use don't use macro for useless stuff, like `ll` could be a typedef... – Jaffa Apr 20 '20 at 18:14
  • 3
    **Recommended reading:** [Why should I not #include ?](https://stackoverflow.com/q/31816095/560648) – Asteroids With Wings Apr 20 '20 at 18:17
  • 1
    Use your debugger to narrow down the problem. – Asteroids With Wings Apr 20 '20 at 18:18
  • 2
    What is this code suppose to do? what do you expect out respect to what you put in? we need this information to help you debug – james Apr 20 '20 at 18:18
  • 1
    *Here for input: 1 4 10 garbage value is coming why?* -- If you know the input that fails, why are you not putting that input into the code itself? There should be no `cin` statements in the code you posted -- you should be assigning the variables with the faulty test case. Remember that we are not the online judge website -- you should take the code, remove all of the stuff like "sync_with_stdio", use the proper headers, get rid of the crazy macros like `ll`, and if you know the test data, *put the test data in the program by assigning the variables with the test data*. – PaulMcKenzie Apr 20 '20 at 18:22
  • 1
    You need to improve your coding standards or guidelines. This style of code would not pass a professional code inspection. If you are doing the online exercises for education, you should employ good coding styles. – Thomas Matthews Apr 20 '20 at 18:23
  • This is pretty standard USACO solution code style. – Aplet123 Apr 20 '20 at 18:27
  • 2
    @Aplet123 This is not an online competition [to produce the worst possible code in the least possible time], it is a Q&A for professional developers. So some translation is required. OP can always convert it back before submission, after locating their bug. – Asteroids With Wings Apr 20 '20 at 18:27
  • @OP [This is what should have been posted](http://coliru.stacked-crooked.com/a/55ad80501d5e2b40). – PaulMcKenzie Apr 20 '20 at 18:30

1 Answers1

1

I'm not sure what the correct output should be, But it looks like you have an overflow. In pow function you calculate the whole result then take the mod. Since the result may be very big to even fit in long long, it overflows before taking the mod, thus having a wrong answer. A simple solution to this is to implement a Pow function that takes the mod whenever it multiplies. The code have some other problems such as importing bits/stdc++.h, using namespace std, ll and M.... but that's irrelevant. But I suppose this code is for some problem solving contest.

Code with the problem probably solved:

#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";
    }
}

Input:

1 4 10

Output:

707919736
StackExchange123
  • 1,871
  • 9
  • 24