APOWBMODC - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: harsh_h
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Math

PROBLEM:

You’re given an integer A that doesn’t exceed 10^9.
Find integers B, C such that A \lt B \lt C \leq 10^{18}, and:

  • A^B is a multiple of C and B^C is a multiple of A.

EXPLANATION:

It seems fairly hard to control both A^B\pmod{C} and B^C\pmod{A} simultaneously.
So, let’s try to eliminate having to think about one of them: in particular, since B\gt A, notice that as long as B is a multiple of A, B^C will always be a multiple of A, no matter what C is.

Let’s try and choose B to be a multiple of A, say B = k\cdot A. Independent of what k is, the second equation is now guaranteed to be true.
We also currently have no restrictions on C.

Plugging our choice into the first equation, we have A^B = A^{k\cdot A} = (A^A)^k, which we want to be a multiple of C.
It’s easy to see that simply choosing C = A^A will make this true independent of our choice of k.
Since we need B to lie strictly between A and C, we can now choose k to be any integer from 2 to A-1.
For convenience, let’s choose k = 2.

We now have a fairly simple solution: B = 2A and C = A^2.
Clearly B\gt A, and as long as A\gt 2 we also have C\gt B.
Further, C \leq 10^{18}, so there are no issues with limits.

The only remaining case is when A = 2, in which case the above solution doesn’t work.
However, that’s a single small case, and is easily solved by hand.
For instance, choose B = 4 and C = 16, so that A^B = 2^4 = 16 is a multiple of C, and B^C = 4^{16} is even and so a multiple of 2.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Author's code (C++) 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
ll mod_inv(ll a, ll m) {
    ll g = m, r = a, x = 0, y = 1;
    while (r != 0) {
        ll q = g / r;
        g %= r; swap(g, r);
        x -= q * y; swap(x, y);
    }
    return (x%m + m)%m;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll t;cin>>t;

    while(t--){
        ll a;cin>>a;
        if(a==2) cout<<4<<" "<<8<<endl;
        else cout<<2*a<<" "<<a*a<<endl;
    }
}
Editorialist's code (Python) 
for _ in range(int(input())):
    a = int(input())
    if a > 2: print((a-1)*a, a*a)
    else: print(10, 1024)
1 Like