I want to view all solution for: X^12≡1(mod27) So I wrote the following C program which outputs only 1 even though 8 and 10 are possible values for x too.
Why is that?
#include <iostream>
#include <cmath>
int main() {
for (int i = 0; i <= 2700000; i) {
if (int(pow(i, 12))% 27 == 1) {
std::cout << i << std::endl;
}
}
std::cout << "Hello, World!" << std::endl;
return 0;
}
CodePudding user response:
The inbuild pow()
function is not capable of handling so large number.
Rather we have to use custom function to achieve that.
Here it is
#include <iostream>
#include <cmath>
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
int main() {
for (int i = 0; i <= 2700000; i) {
if (binpow(i, 12, 27) == 1) {
std::cout << i << std::endl;
}
}
std::cout << "Hello, World!" << std::endl;
return 0;
}
You can read more about that function from here: https://cp-algorithms.com/algebra/binary-exp.html
CodePudding user response:
Oh, that's because you're using int
s to calculate 12th powers, which are very large numbers. Int can only store numbers up to 2147483647, so use long long ints instead which can be much larger.
I rewrote your code and got this output: 1 8 10 17 19 26 28
#include <iostream>
#include <cmath>
int main()
{
for (int i = 0; i <= 2700000; i)
{
long long int power = pow(i, 12);
int mod = power % 27;
if (mod == 1)
std::cout << i << std::endl;
}
std::cin.get();
return 0;
}