国际大学生程序设计竞赛例题_5.19原子能转变

1,问题:u+a1y1+a2y2+a3y3+a4y4=v+a1z1+a2z2+a3z3+a4z4
y1+y2+y3+y4=z1+z2+z3+z4;
判断是否有整数解.
2,解答:
令x1=y1-z1,...问题转化为(a1-a4)x1+(a2-a4)x2+(a3-a4)x3=v-u是否有整数解
定理:a1x1+...+anxn=N,其中a1...N都是整数,n>=2.a1..an都不等于0,则该式有解的充要条件是:(a1,...,an)的最大公约数可以被N整除.
3,题意:输入a1到a4,min和max限定u和v的范围
输出:u和v取任意值,共有多少整数解.
假定最大公约数为g,整数解得个数=abs(u-v)/g.u-v=0的可能有max-min+1种
4,代码

#include <iostream>
using namespace std;

int a1,a2,a3,a4,mmin,mmax;
long long ans;

int gcb(int x,int y) //返回最大公约数
{
    return y? gcb(y,x%y):x;
}

int main()
{
    freopen("5.19.in","r",stdin);

    int g,cnt;
    cin>>cnt;
    while(cnt--)
    {
        ans=0;
        g=0;
        cin>>mmin>>mmax>>a1>>a2>>a3>>a4;
        a1-=a4;a2-=a4;a3-=a4;
        //求a1,a2,a3的最大公约数
        //小心a1,a2,a3可能为0
        if(a1) g=g? gcb(g,a1):a1;
        if(a2) g=g? gcb(g,a2):a2;
        if(a3) g=g? gcb(g,a3):a3;
        if(g==0) //系数都是0
            cout<<mmax-mmin+1<<endl;
        else
        {
            if(g<0) g=-g;
            //遍历u-v的所有取值
            for(int i=1;i<=mmax-mmin;i++)
                ans+=i/g;
            //正负两种情况,加上u-v==0的情况
            ans=ans*2+mmax-mmin+1;
            cout<<ans<<endl;
        }
    }
    return 0;
}