Orange Boy Can You Solve It Out? Ep. 32
思考题 in one sentence
Yet Another Easy Problem
Find any positive integer pair a,b so that (a+b)+(a+b)\mod k=n where k,n are given or -1 -1 if not found.
Examples
Input
K=100 N=268
Output
200 34
Explain
200+34+(200+34)mod 100=234+34=268
Input
K=100 N=101
Output
-1 -1
Constriants
Subtask 1(10%):N,K=100
Subtask 2(10%):N,K<=1000
Subtask 3(10%):N,K<=1e5
Subtask 4(30%):log_{10}K is an integer.
Subtask 5(20%):K is a prime
Subtask 6(20%):1<=N,K<=1e9
版权声明：
作者：XGN
链接：https://blog.hellholestudios.top/archives/333
来源：Hell Hole Studios Blog
文章版权归作者所有，未经允许请勿转载。
THE END
二维码
Peeper
Let a + b = pk + q (0 < q < k), then we have
pk + 2q = n
Let n = p’k + w’ (0 < q’ < k), then we have
pk + 2q = p’k + q’
(p - p’)k = q’ - 2q
thus
q’ ≡ 2q (mod k).
As 0 < q’, q < k, we know that 2q = q’ or 2q = q’ + k.
We take this two possible values of q’ into the original formula.
① If q’ ≡ 0 (mod 2), then any a, b satisfying
a + b = n - q’ / 2 (for example, let a = 1)
is a valid answer （except when n = 1)
② Otherwise if q’ + k ≡ 0 (mod 2), try
a + b = n - (q’ + k) / 2
and check if it’s valid.
admin@Peeper
You are so clever! This problem maybe the easiest one of all OBCYSIO! Even me can solve it 🙂