POJ 2115.C Looooops“编程开发”

AC代码(C++):

#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 

#define INF 0xfffffff
#define MAXN 100105

using namespace std;

long long A,B,C,k;

void exgcd(long long a, long long b, long long &d, long long &x, long long &y)  
{  
    if(!b){d=a; x=1; y=0;}  
    else  
    {  
        exgcd(b, a%b, d, y, x);  
        y-=x*(a/b);  
    }  
}

int main(){
	while(scanf("%lld%lld%lld%lld",&A,&B,&C,&k)){
		if(A+B+C+k==0)break;
		long long a,b,c,d,x,y;
		a = C;
		b = (long long)1<
总结: 设循环了x次, A超过2^k(即loop)了y次, 则可以得到表达式Cx-(2^k)y=B-A. 这是一个不定方程, 可能有多种解, 而我们要求的是使x最小的那个解. 扩展欧几里得算法就是专门求形如ax+by=c的一个特殊的解的方法, 顺带求出a和b的最大公约数:
 
 

对形如ax+by=c的方程, 用扩展欧几里得算法求出x, y以及a, b的最大公约数d. 如果c%d!=0则无解, 如果有解, 则求x的最小值x0: 设dm=b/d, 则x0=((x*c/d)%dm+dm)%dm.