关于丧心病狂的韩信大点兵的近10条评论(全部评论)
为啥板子跑起来时间都会有差别= = Hzoi_Mafia 2017-07-12 13:58 6楼
蒟蒻的我居然输出了所有数的LCM，结果样例都得调10分钟。。 _Itachi 2016-11-17 07:17 5楼
这个保证有解是肯定的，因为我找了一些非常大的数然后随机一堆数取模，所以-1骗不了分。不是质数的情况就要分解质因数取所有质数的指数的最高项即可（因为$x$ $mod$ $a$ $= c$,$x$ $mod$ $b$ $=$ $c$,则$x$ $mod$ $lcm(a,b) = c$,$lcm$为最小公倍数）而$(2^1,2^5,...... 2^x)$最小公倍数肯定是$2^{max(x)}$，所以我们取新的$P_i$为$2^{max(x)}$即可，然后让使得取得最高项的$A_i$ $mod$ 新的$P_i$作为新的$A_i$,这样的话所有的$P_i$必定互质，构造出新的方程后就按一般互质的情况计算即可例如下面一组数据： 10 40 39 60 19 14 1 95 39 9 7 85 59 87 55 88 63 96 31 5 4 我们进行转换后得 32 31 //2^5 from 96 31 9 7 //3^2 from 9 7 5 4 //5^1 from 5 4 7 1 //7^1 from 14 1 11 8//11^1 from 88 63(63 mod 11 =8) 17 8//17^1 from 85 59(59 mod 17=8) 19 1//19^1 from 95 39(39 mod 19 =1) 29 26//29^1 from 87 55(55 mod 29=26) Satoshi 2016-06-30 18:18 4楼
膜法合并 cstdio 2016-02-23 17:25 3楼
暴力枚举70%估计是极限了，目测就算用上qread和qwrite也没法80%... Hzoi_ 2016-02-16 16:28 2楼
暴力枚举法能优化到70%我已经尽力了... Hzoi_ 2016-02-16 16:18 1楼

2160. 丧心病狂的韩信大点兵

★★★ 输入文件：weakhanxin.in 输出文件：weakhanxin.out 简单对比
时间限制：1 s 内存限制：256 MiB

韩信是中国军事思想“谋战”派代表人物，被后人奉为“兵仙”、“战神”。“王侯将相”韩信一人全任。“国士无双”、“功高无二，略不世出”是楚汉之时人们对其的评价。作为统帅，他率军出陈仓、定三秦、擒魏、破代、灭赵、降燕、伐齐，直至垓下全歼楚军，无一败绩，天下莫敢与之相争。

相传，韩信带兵打仗时，从不直接清点军队人数。有一次，韩信带1500名兵士打仗，战死四五百人。站3人一排，多出2人；站5人一排，多出4人；站7人一排，多出6人。韩信马上说出人数：1049。

但是Asm.def第一次穿越到过去遇到的是战神韩信，而Satoshi和Asm.def一起穿越到过去遇到的是M18星云来的战五渣韩信。

战神韩信用素数点兵，战五渣韩信用正整数点兵。

这次，项羽派韩信带兵攻打一座重兵驻扎的城市。城市占领了，可楚军也是伤亡惨重。韩信需要知道楚军至少还剩下多少人，好向范增汇报。

已知韩信发出了$M$次命令，对于第i次命令，他选择一个正整数$P_i$，要求士兵每$P_i$人站一排，此时最后一排剩下了$a_i$人。你的任务是帮助韩信求出这种情况下楚军兵力的最小值。

Asm.def和Satoshi为了改变历史进程，穿越到过去的另一个平行宇宙，在这个平行宇宙，韩信投奔了项羽，我们的任务就是帮助楚国获得胜利，使得汉朝不存在，从而明朝不会灭亡，从而中国不会沦为半殖民地半封建社会，从而没有GCD和金三胖......

Asm.def上尉：垃圾任务，中国单身狗定理随随便便就能解决啦！

韩信说：你再仔细读题，没有保证所有$P_i$不互质，你根本用不成中国剩余定理，乖乖打30分的质数骗分或者暴力枚举吧！

Asm.def:我在人工智能摸爬滚打了这么多年，经历了那么多生与死的瞬间，用C4突破过绿坝长城，用菜刀刺杀过方教授，帅死过金三胖，大长腿征服过一个连得妹子，你这点小问题岂能难得倒我？

Asm.def偷偷对Satoshi说:我屮艸芔茻！你最近不是在学数论吗？这我还真不会了，你快想办法！我一代顶级朝阳广场舞大妈首领（中国顶级特务机构）的名声不能就这样。。。。。。

Satoshi:

所有数据保证有解。

第一行两个正整数$M$，代表韩信的询问次数。

接下来有$M$行，每行两个非负整数$P_i，a_i$，代表韩信选择的数和此时剩下的人数。

输入保证每个$P_i$各不相同。

输出一行，一个整数。

输出最小人数.

2
4 3
5 1

$ 对于30 \%的数据,P_i是素数. 1 \leq P_i \leq 200,000,\,\, 1\leq M \leq 4;$

$ 对于100 \%的数据，1 \leq P_i \leq 200,000,\,\,1 \leq M \leq 20;\\保证所有P_i的乘积 \le 10^{20}, 0 \le a_i < P_i.$

$ 原题ID:1786$