d.对于这个循环，

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

给出A，B，C，求在k位存储系统下的循环次数。

例如k=4时，变量variable则只在0~15之间循环变化。

 

s.扩展欧几里德求解模线性方程（线性同余方程）。

设循环次数为x，

1.(A+C*x)mod 2^k=B. --> C*x=B-A(mod 2^k). （怎么变来的？）

2.C*x=B-A(mod 2^k). --> C*x+(2^k)*y=B-A.

扩展欧几里德求：C*x+(2^k)*y=gcd(C,2^k)=d.（原式：a*x+b*y=gcd(a,b)=d，以下a代表C，b代表2^k。）

如果(B-A)mod d==0（也就是(B-A)的值可以整除d，貌似表示为d|(B-A)？），则原方程C*x+(2^k)*y=B-A.的解为x'=x*((B-A)/d)。

3.利用周期性变化，求出最小的非负整数解为x''=(x'%(b/d)+(b/d))%(b/d).

因为：如果C*x+(2^k)*y=B-A.的一组整数解为(x1,y1)，则它的任意整数解为(x1+k*(b/d)),y1-k*(a/d)).(k取任意整数)

（1）x'%(b/d)，使解在(-b/d,b/d)

（2）+(b/d)，使解在(0,2*b/d)

（3）%(b/d)，得到最小整数解

 

为什么b/gcd(a,b)，a/gcd(a,b)分别为x，y的解的最小间距？

解：假设c为x的解的最小间距，此时d为y的解的间距，所以x=x0+c*t，y=y0-d*t（x0，y0为一组特解，t为任意整数）

      带入方程得：a*x0+a*c*t+b*y0-b*d*t=n,因为a*x0+b*y0=n，所以a*c*t-b*d*t=0，t不等于0时，a*c=b*d

      因为a,b,c,d都为正整数，所以用最小的c，d，使得等式成立，ac，bd就应该等于a，b的最小公倍数a*b/gcd(a,b),

      所以c=b/gcd(a,b)，d就等于a/gcd(a,b)。

 

若最后所求解要求x为最小整数，那么x=(x0%（b/gcd(a,b))+b/gcd(a,b))%(b/gcd(a,b))即为x的最小整数解。

x0%（b/gcd(a,b))使解落到区间-b/gcd(a,b)~b/gcd(a,b)，再加上b/gcd(a,b)使解在区间0~2*b/gcd(a,b)，

再模上b/gcd(a,b)，则得到最小整数解（注意b/gcd(a,b)为解的最小距离，重要）

c.

#include
      
       #include
       
        using namespace std;//返回d=gcd(a,b);和对应于等式ax+by=d中的x,ylong long extend_gcd(long long a,long long b,long long &x,long long &y){    if(a==0&&b==0)return -1;//无最大公约数    if(b==0){x=1;y=0;return a;}    long long d=extend_gcd(b,a%b,y,x);    y-=a/b*x;    return d;}//求逆元//ax=1(mod n)long long mod_reverse(long long a,long long n){    long long x,y;    long long d=extend_gcd(a,n,x,y);    if(d==1)return (x%n+n)%n;    else return -1;}int main(){    long long A,B,C,k;    long long a,b,x,y;    long long d;    while(~scanf("%lld%lld%lld%lld",&A,&B,&C,&k)){        if(A==0&&B==0&&C==0&&k==0)break;        a=C;        b=((long long)1)<
       
      

 

ps:题解可以参考这个： 当时就是看这个才懂的