题目链接 题意：给出p, q, e, l,令n = p * q, fn = (p-1) * (q-1) 给出l个c,计算m = D(c) = c**d** mod n,其中m为要输入的明文对应的ascii编码，d的计算方法：> calculate d, making d × e mod F(n) = 1 mod F(n), and d will be the private key。 问明文。 思路： 出题人JGShining（极光炫影）傻逼。 题意都说不清？ 大小写字母一个意思？ 脑袋有坑的出题人。 出题人傻逼。 出题人傻逼。 出题人傻逼。 好了。这道题需要用到扩展欧几里得算法求逆元。。。ksm(a,mod-2)的方法是基于 …

题目链接 题意：求在小于等于N的正整数中有多少个X满足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)。 思路：先用扩展欧几里得算法（excrt）解一般同余方程求出一个特解R,然后通解R' = R + k * LCM(a1..am) 注意一些特殊情况，如果无解输出0，如果n小于最小的正整数的R也输出0， 否则答案为(n-R)/M + 1 /* *********************************************** Author :111qqz …

题目链接 题意：给出k个方程，形式为 x==r1,求最小的正数x，无解输出-1. 思路：首先很容易让人联想到crt. 然而crt的使用条件是，所有的m(也就是这道题中的a)两两互质，这道题并不满足，因此不能使用crt. X mod m1=r1 X mod m2=r2 ... ... ... X mod mn=rn 首先，我们看两个式子的情况 X mod m1=r1……………………………………………………………(1) X mod m2=r2……………………………………………………………(2) 则有 X=m1k1+r1………………………………………………………………() X=m2k2+r2 那么 m1k1+r1=m2k2+r2 整理， …

题目链接 题意：给出a,b,d，分别表示a,b两种刻度的砝码，以及要称量的物体重量为d.现在保证能称量出给定重量的物体，问两种砝码个数的和最小的时候，两种砝码分别有多少。如果有多组解，那么要求weight of(ax + by) 最小。 思路：求特解直接扩展欧几里得... 关键是怎么找到绝对值和最小的。。 我就是两个方向跑了下。。。 一开始因为把weight of (ax+by) （求得还是绝对值最小）理解成了 ax+by最小。。导致WA了半天。。。。sigh.... /* *********************************************** Author :111qqz Created Time :Thu …

题目链接 题意： 问 循环for ( int i = a ; i !=b; i+=c)在% （2^k）的意义下循环了多少次。 思路： 一般的思路是： 列方程... 化成扩展欧几里得算法的形式。。。 根据裴蜀定理判断解是否存在... 然后用对用扩展欧几里得算法求出的X,Y按照题目要求调整。 /* *********************************************** Author :111qqz Created Time :Thu 13 Oct 2016 03:57:06 PM CST File Name :code/poj/2115.cpp …

题目链接 题意：两只青蛙初始在数轴的x,y点，单位时间内分别可以向右跳m米和n米，数轴是环型的，长度为L，问两只青蛙能否相遇，以及相遇时跳的次数。 思路：相遇就是同一时间在同一地点。  那么有方程 x+ Cm = y + Cn + k*L 其中C为跳的次数，k为之间差了L的个数（可以理解为被套圈的圈数） 化简得到 C(m-n) + K*L = y-x. 根据裴蜀定理，该方程有解，当且仅当y-x是gcd(m-n,L)的倍数。 然后根据扩展欧几里得算法，需要注意的是其中可能有负数。 如果a是负数， …

题目链接 题意：问ax+by=1的一组x>0的解，如果无解输出sorry. 思路：根据裴蜀定理， ax+by=1有解当且gcd(a,b)=1。 然后根据扩展欧几里得算法，我们可以得到一组x,y。需要注意的是，这只是其中一组解。 x,y的通解为：**(x+kgx , y-kgy ） 其中：gx= b/gcd(a,b),gy = a/gcd(a,b),k为任意整数 ** /* *********************************************** Author :111qqz Created Time :Wed 12 Oct 2016 07:30:20 PM CST File Name …

前置技能点： 维基百科_裴蜀定理（贝祖等式） 对任何[整数](https://zh.wikipedia.org/wiki/) ，  和它们的[最大公约 …