-1

I am trying to solve a problem. where the user will give the input an integer then squaring it I have to find the mod. But when I give big integer pow() is giving the wrong answer. How can i fix that?

#include<bits/stdc++.h>

using namespace std;

int main()
{
    //ios_base:: sync_with_stdio(false);
    //cin.tie(NULL);
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {

        long long  n;
        cin>>n;

        long long  sn=0;
        sn=pow(n,2);
        long long v = pow(10,9)+7;

        cout<<sn%v<<endl;

    }
}
imtinan
  • 181
  • 7
  • 4
    `pow` works on floating point numbers, not integers, so you always have to deal with problems related to floating point precision, if you use `std::pow` – t.niese Jun 02 '20 at 08:15
  • 4
    The `pow` function computes floating point numbers, so your integer are converted into floating point numbers. Floating point numbers can only store integers upto a given size accurately. `10^9` crosses that limit. – kvantour Jun 02 '20 at 08:15
  • [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) – Evg Jun 02 '20 at 08:26
  • 2
    Just don't use pow. `sn=pow(n,2);` should be `sn=n*n;` and `long long v = pow(10,9)+7;` should be `int v = 1000000007;` – Yksisarvinen Jun 02 '20 at 08:27

2 Answers2

1

As the comments say, pow works on floating numbers. Since you want to square integers, you're better off just multiplying them together using sn = n*n. If you use an unsigned long long you'll be able to exactly compute the square but only if this square is at most +18,446,744,073,709,551,615 (see https://en.m.wikipedia.org/wiki/C_data_types)

Shersher
  • 67
  • 1
  • 6
0

The trick to solve this problem is computing the modulus earlier. Modular arithmetic offers some opportunities for this.

For this question note that (a * b) % m == (a % m) * (b % m).

Moreover 1000000007^2 does still fit within a 64 bit int, so the result will at all times be small enough.

Hence the relevant part of the code could look as follows

const int64_t m = 1000000007;
int64_t n;
cin>>n;

n = n % m;
int64_t sn = n * n;
sn = sn % m;

cout << sn << endl;
user3177387
  • 41
  • 2
  • 4