Challenge: Minion of the Year
Subdomeniu: Number Theory (number-theory)
Scor cont: 120.0 / 120
Submission status: Accepted
Submission score: 1.0
Submission ID: 464775701
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/minion-of-the-year/problem
Cerinta
Gru wanted to upgrade the quality of his minions' despicableness through his new base, The Volcano. Dave, desperately wanting the *Minion of the Year* award, rushed to The Volcano only to find out that he needs to solve a series of questions before he can unlock the gate and enter.
Dave is given a prime $P$, and $N$ questions.
In each question/query, Dave is given four integers $(A, B, C, D)$, and Dave needs to find the minimum possible value of $Ax + By$ among all positive integer pairs $(x,y)$ such that $P$ divides $\left|C^x - D^y\right|$.
Unfortunately, the gate has a strict time limit, and if Dave is unable to answer all questions quickly and correctly, then a hidden freeze ray will zap him and he won't be able to move. Please help Dave answer all the questions so he can enter The Volcano and win the Minion of the Year award!
**Input Format**
The first line of input consists of an integer, $T$, which is the number of test cases.
The first line of each test case consists of two integers separated by a space, $P$ and $N$. The following $N$ lines contain the queries, each in a line. Each question consists of four integers separated by single spaces: $A$, $B$, $C$ and $D$.
**Output Format**
For each query, output a single line containing the minimum value of $Ax + By$, or output `wala` if no such pairs $(x,y)$ exist.
**Constraints**
$1 \le T \le 3$
$1 \le N \le 6000$
$2 \le P \le 10^8$
$0 \le A, B, C, D \le 10^8$
$P$ is prime
**Sample Input**
2
7 2
1 1 1 5
7 8 8 7
11 5
1 1 1 1
0 1 2 3
3 2 1 0
9 8 7 6
0 0 1 1
**Sample Output**
7
wala
2
1
wala
33
0
**Explanation**
For the first query, $P = 7$, $(A, B, C, D) = (1, 1, 1, 5)$, the minimum $1x + 1y$ is $7$, which occurs at $(x,y) = (1,6)$ ($7$ divides $\left|1^1 - 5^6\right| = 15624 = 7\cdot 2232$).
For the second query, no matter what $(x,y)$ you choose, $\left|8^x - 7^y\right|$ will not by divisible by $7$, so the answer is `wala`.Cod sursa
#include <bits/stdc++.h>
using namespace std;
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define F first
#define S second
typedef long long LL;
int MOD, root, half, hv;
const int SIZE = 1e6 + 10;
vector<pair<int, int>> pp;
LL mypow(LL x, LL y){
LL res = 1;
while(y){
if(y & 1) res = res * x % MOD;
y >>= 1;
x = x * x % MOD;
}
return res;
}
int find_root(int P){
if(P == 2) return 1;
vector<int> fac;
for(int i = 2; i * i <= P - 1; i++){
if((P - 1) % i == 0) fac.PB(i), fac.PB(P / i);
}
int now = 2;
while(1){
bool err=0;
REP(i, SZ(fac)){
if(mypow(now, fac[i]) == 1){
err = 1;
break;
}
}
if(!err) break;
now++;
}
return now;
}
void pre(int P){
root = find_root(P);
int now = 1;
pp.clear();
pp.PB(MP(1, 0));
for(int i = 1; i < P - 1 && i <= 1000000; i++){
now = (LL)now * root % P;
pp.PB(MP(now, i));
half = i;
hv = now;
}
hv = mypow(hv, MOD - 2);
sort(ALL(pp));
}
int get_id(int x){
int ans = 0, it;
while(1){
it = lower_bound(ALL(pp), MP(x, 0)) - pp.begin();
if(it != SZ(pp) && pp[it].F == x) break;
ans += half;
x = (LL)x * hv % MOD;
}
return pp[it].S + ans;
}
struct gcd_t {LL x, y, z;};
gcd_t gcd(LL a, LL b) {
if(b==0) return (gcd_t){1, 0, a};
gcd_t t = gcd(b, a % b);
return (gcd_t){t.y, t.x - t.y * (a / b), t.z};
}
int main(){
CASET{
DRII(P, N);
MOD = P;
pre(P);
while(N--){
DRII(A, B);
DRII(C, D);
if(A < B){
swap(A, B);
swap(C, D);
}
if(C % P == 0 && D % P == 0){
printf("%d\n", A + B);
}
else if(C % P == 0 || D % P == 0) puts("wala");
else{
C %= P;
D %= P;
if(P == 2){
printf("%d\n", A + B);
continue;
}
C = get_id(C);
D = get_id(D);
if(C == 0 && D == 0){
printf("%d\n", A + B);
continue;
}
else if(C == 0){
int gg = __gcd(D, P - 1);
printf("%lld\n", A + (LL)B * (P - 1) / gg);
continue;
}
else if(D == 0){
int gg = __gcd(C, P - 1);
printf("%lld\n", B + (LL)A * (P - 1) / gg);
continue;
}
int M = P - 1;{
int ha = __gcd(C, __gcd(D, M));
C /= ha; D /= ha; M /= ha;
}
int gg1 = __gcd(D, M);
int M2 = M / gg1;
LL now1 = gg1 / __gcd(gg1, C);
gcd_t ker = gcd(D, M);
while(ker.x < 0) ker.x += M2;
LL now2 = C * now1 / ker.z % M2 * ker.x % M2;
D = now1;
C = now2;
if(now2 == 0) now2 = M2;
LL mi = A * now1 + B * now2;
while((LL)A * (now1 + D) < mi){
now1 += D;
now2 += C;
if(now2 > M2) now2 -= M2;
mi = min(mi, A * now1 + B * now2);
}
cout << mi << endl;
}
}
}
return 0;
}
HackerRank Number Theory – Minion of the Year