poj2115(扩展欧几里得运用)

题意：求for(int i=a;i!=b;i+=c,i%=(1<<k))执行的次数；

解法：即求解C*x-(1<<k)*y=b-a;即C*x+K*y=b-a；如果g=gcd(C,K)不能被b-a整除，则说明无解。

         用exgcd()求出一组C/g*x+K/g*y=1的解，然后两边乘上(b-a)/g将求出的x取最小正数输出。

代码：

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-8
const double pi=acos(-1.0);
typedef long long LL;
const int Max=10100;
const int INF=1000000007;

LL A, B, C, k;
LL exgcd(LL m,LL n,LL &x,LL &y)//求解方程mx+n*y=1的一组解（m，n已知，并且默认m，n互质）方程要灵活运用
  {
      LL x1,y1,x0,y0;
      x0=1; y0=0;
      x1=0; y1=1;
      x=0; y=1;
      LL r=m%n;
      LL q=(m-r)/n;
      while(r)
    {
         x=x0-q*x1; y=y0-q*y1;
         x0=x1; y0=y1;
         x1=x; y1=y;
         m=n; n=r; r=m%n;
         q=(m-r)/n;
     }
     return n;
 }
LL gcd(LL a,LL b)
{
    return (a==0)?b:gcd(b%a,a);
}
int main()
{
  while(cin>>A>>B>>C>>k)
  {
      if(A==0&&B==0&&C==0&&k==0)
        break;
      k=LL(1)<<k;
      LL x,y;
      LL g=gcd(C,k);
      if((B-A)%g!=0)
      {
          cout<<"FOREVER\n";
          continue;
      }
     exgcd(C/g,k/g,x,y);
     k/=g;
     cout<<((x*(B-A)/g%k)+k)%k<<endl;
  }
   return 0;
}

poj2115(扩展欧几里得运用),布布扣,bubuko.com

poj2115(扩展欧几里得运用)

原文：http://blog.csdn.net/xiefubao/article/details/26376953