51 lines
947 B
C
51 lines
947 B
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
typedef unsigned __int128 uint128;
|
|
typedef unsigned long long int uint64;
|
|
|
|
uint64 l[] = {
|
|
4611686018427394499,
|
|
4611686018427395927,
|
|
4611686018427402023,
|
|
4611686018427402599,
|
|
4611686018427407519,
|
|
4611686018427407939,
|
|
4611686018427408827,
|
|
4611686018427412487,
|
|
4611686018427412619,
|
|
4611686018427413183,
|
|
4611686018427415163,
|
|
4611686018427419483,
|
|
4611686018427419627,
|
|
4611686018427427067,
|
|
};
|
|
|
|
uint64 expm(uint64 m, uint64 e, uint64 mod)
|
|
{
|
|
uint128 _r=1;
|
|
uint128 _m=(uint64)m;
|
|
uint128 _mod = (uint64)mod;
|
|
|
|
while (e > 0) {
|
|
if ((e & 1) > 0) _r = (_r * _m) % _mod;
|
|
e >>= 1;
|
|
_m = (_m * _m) % _mod;
|
|
}
|
|
|
|
return (uint64)_r;
|
|
}
|
|
|
|
uint64 generateur(uint64 p)
|
|
{
|
|
uint64 g=2;
|
|
uint64 r=1;
|
|
|
|
while(g < p - 1) {
|
|
r = expm(g, (p-1)/2, p);
|
|
if(r != 1)
|
|
return g;
|
|
g++;
|
|
}
|
|
return 0;
|
|
} |