D:C Looooops
题目数据范围很大,显然不能用模拟,但是可以用求不定方程来得出答案,关键是要用int64(long long)
模型:求 a+cx=b(mod 2^k) 最小正整数解 (0=<a,b,c<2^k,这个范围比较重要)
我们通过扩展欧几里德求得一解 x,(无解就输出FOREVER)
x%=(2^k/d),if(x<0) x+==(2^k/d).x为答案。
网上的讲法很多,有叫欧几里德扩展法,也有叫线性同余的,感觉思路都是一样的。关键就在判断是否有解(即是否为FOREVER)。
(第一次写解题报告。。。有水分。。)