POJ2115 C Looooops(拓展欧几里德)

墨蓝 2021-12-20 23:11 202阅读 0赞

题意：

要求a不断加c到达b，如果a大于2^k就mod2^k，求最少要加几次c。

要点：

拓展欧几里德算法求最小整数解，就是个模板。不过要注意计算2^k时因为超出int范围所以必须先强制类型转换：(\_\_int64)1 << k。

<table style="border-collapse:collapse;font-family:'Times New Roman', Times, serif;"> 
 <tbody> 
  <tr> 
   <td>15409053</td> 
   <td><a href="http://poj.org/userstatus?user_id=Seasonal" style="text-decoration:none;" rel="nofollow">Seasonal</a></td> 
   <td><a href="http://poj.org/problem?id=2115" style="text-decoration:none;" rel="nofollow">2115</a></td> 
   <td><span style="color:#0000FF;">Accepted</span></td> 
   <td>164K</td> 
   <td>0MS</td> 
   <td><a href="http://poj.org/showsource?solution_id=15409053" style="text-decoration:none;" rel="nofollow">C++</a></td> 
   <td>633B</td> 
   <td>2016-04-19 09:20:54</td> 
  </tr> 
 </tbody> 
</table>

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    __int64 e_gcd(__int64 a, __int64 b, __int64 &x, __int64 &y)
    {
    	__int64 ans, temp;
    	if (b == 0)
    	{
    		x = 1; y = 0;
    		return a;
    	}
    	ans = e_gcd(b, a%b, x, y);
    	temp = x;
    	x = y;
    	y = temp - a / b*y;
    	return ans;
    }
    
    int main()
    {
    	__int64 a, b, c,d,k,xx,yy,r,num;
    	while (scanf("%I64d%I64d%I64d%I64d", &a, &b, &c, &k))
    	{
    		if (!a && !b && !c && !k)
    			break;
    		num = (__int64)1 << k;		//这里要强制类型转换，毕竟有个1不是__int64型的
    		d = e_gcd(c, num, xx, yy);
    		if ((b - a) % d != 0)
    			printf("FOREVER\n");
    		else
    		{
    			xx *= (b - a) / d;
    			r = num / d;
    			xx = (xx%r + r) % r;
    			printf("%I64d\n", xx);
    		}
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/seasonal/p/10343770.html