数论青蛙的约会扩展欧几里得-白红宇

数论青蛙的约会扩展欧几里得

阅读量：5339 次

发布时间：2019-06-15

本文共 3333 字，大约阅读时间需要 11 分钟。

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

Input

输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。

Output

输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"

Sample Input

1 2 3 4 5

Sample Output

4 这个题目是一个扩展欧几里得，一开始还没有看出来，自己的公式列错了，后来看出来之后，取模又没有取好，不过现在都解决了， 接下来我说一下这个题目的具体解题过程吧。 这个开始可以推得公式 n*t+y=x+m*t (mod l) 所以就可以化简成 (n-m)*t≡ x-y (mod l) 然后我们令a=n-m b=x-y 所以就可以转化成 a*t=b mod l 这个就是扩展欧几里得的求解 线性同余方程 的应用 这个不明白的可以看这个博客： 接下来说说线性同余方程过程 a*x≡b mod n 这个可以转化成 a*x+n*y=b (因为y不是需要得到的值，所以无所谓正负，不然这个应该是 a*x=n*y+b 换过去应该是有个负号的 然后你就会发现这个与扩展欧几里得的式子很像：a*x+n*y=gcd(a,n) 所以上面式子要求x，和下面式子求x，y差不多。 已知：如果一个方程a*x+b*y=c 如果gcd(a,b)|c 那么这个方程则有整数解，反之则没有。 所以我们要求整数解，那么说明gcd(a,n)|b 如果不整除，则说明输出Impossible 然后就很简单了，我们求出 扩展欧几里得的解，然后 就可以得到上式的解为 ans=x*b/gcd(a,n) 这个只是一个解，不一定是最小的正整数解，那么该如何取这个最小的正整数解呢？

定理二：若gcd(a, n) = 1，则方程ax ≡ c (mod n)在[0, n-1]上有唯一解。

定理三：若gcd(a, n) = d，则方程ax ≡ c (mod n)在[0, n/d - 1]上有唯一解。

这个是两个定理，具体证明过程请参照：

由定理二可得，0~n-1上有唯一的解，但是这个又有点特别，因为这个的n值扩大了，需要缩小

缩小之后的结果就是在0~n/d-1 上有唯一的解，这个证明过程可以参照定理二的证明过程

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #define inf 0x3f3f3f3fusing namespace std;typedef long long ll;const ll maxn = 3e10;ll exgcd(ll a,ll b,ll&x,ll&y){ if(b==0) { x = 1; y = 0; return a; } ll ans = exgcd(b, a%b, x, y); ll tmp = x; x = y; y = tmp - a / b * y; return ans;}int main(){ ll x, y, m, n, l,s1,s2; cin >> x >> y >> m >> n >> l; ll a = n - m, b = x - y; ll d = exgcd(a, l,s1,s2); ll p = l / d; if(b%d!=0) { printf("Impossible\n"); return 0; } ll ans = (s1 * (b / d) % p+p)%p; printf("%lld\n", ans); return 0;}

然后再补充一个题：

A Compiler Mystery: We are given a C-language style for loop of type

for (variable = A; variable != B; variable += C)   statement;

I.e., a loop which starts by setting variable to value A and while variable is not equal to B, repeats statement followed by increasing the variable by C. We want to know how many times does the statement get executed for particular values of A, B and C, assuming that all arithmetics is calculated in a k-bit unsigned integer type (with values 0 <= x < 2 ^k) modulo 2 ^k.

Input

The input consists of several instances. Each instance is described by a single line with four integers A, B, C, k separated by a single space. The integer k (1 <= k <= 32) is the number of bits of the control variable of the loop and A, B, C (0 <= A, B, C < 2 ^k) are the parameters of the loop.

The input is finished by a line containing four zeros.

Output

The output consists of several lines corresponding to the instances on the input. The i-th line contains either the number of executions of the statement in the i-th instance (a single integer number) or the word FOREVER if the loop does not terminate.

Sample Input

3 3 2 163 7 2 167 3 2 163 4 2 160 0 0 0

Sample Output

0232766FOREVER 这个题目和上面的一样的，所以就不说了，当作练习题练练手。

转载于:https://www.cnblogs.com/EchoZQN/p/10692910.html

你可能感兴趣的文章