题目： http://poj.org/problem?id=2115
要求： 会求最优解，会求这d个解，即（x+(i-1)*b/d)modm;(看最后那个博客的链接地址）
前两天用二元一次线性方程解过，万变不离其宗都是利用扩展欧几里得来接最优解。
分析：
数论了解的还不算太多，解的时候，碰到了不小的麻烦。
设答案为x，n = (1<<k), 则 (A+C*x) % n == B
即 (A+C*x) ≡ B (mod n)//-----结果显而易见两边的（a+cx)%n==b<n
化简得 C*x ≡ (B-A） （mod n)//----同余模的性质a-c==b-c(mod n)在a==b(mod n)的前提下
自己晕了，还是掌握的不好，和之前的代码一样，只是推导的方法多了一种。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
long long a,b,c,k;
long long x1,x2;
long long gcd(long long a,long long b)
{
return b==?a:gcd(b,a%b);
}
void extend(long long A,long long B,long long &x1,long long &y1)
{
if(B==)
{
x1=;
y1=;
return ;
}
extend(B,A%B,x1,y1);
long long t=x1;
x1=y1;
y1=t-(A/B)*y1;
}
int main()
{
while(scanf("%lld%lld%lld%lld",&a,&b,&c,&k)!=EOF)
{
if(a==&&b==&&c==&&k==) break;
long long A=c;
long long B=pow(,k);
long long C=b-a;
long long temp=gcd(A,B);
if(C%temp)
{
printf("FOREVER\n");
continue;
}
A/=temp;
B/=temp;
C/=temp;
extend(A,B,x1,x2);
long long t=(C*x1%B+B)%B;
printf("%lld\n",t);
}
return ;
}
一元线性同余方程：形如 ax==b%m;
解法：http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html#2985941