DLKKILL

DLKKILL's world

UVA - 12169 - Disgruntled Judge (exgcd解同余取模方程)

题目链接:UVA – 12169 

题目大意:已知公式:xi=(axi-1+b)mod 10001

                给出奇数项,输出偶数项

题目分析:可以枚举a,利用同余取模方程解出b,(x3-a*a*x1)%mod=((a+1)*b)%mod,

                 化简得((a+1)*x-mod*y=x3-a*a*x1)解出x即可。

                 然后求每一项的值验证a是否正确。

                  (或者直接大暴力枚举a,b,ε=ε=ε=┏(゜ロ゜;)┛

给出代码:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn= 10000+10;
const int MOD=10001;
typedef long long ll;
int T;
long long int nums[maxn*2];
void ex_gcd(ll a,ll b,ll &g,ll &x,ll &y)
{
    if(b==0)
    {
        g=a;
        x=1;
        y=0;
    }
    else
    {
        ex_gcd(b,a%b,g,y,x);
        y-=x*(a/b);
    }
}
int main()
{
    while(cin>>T)
    {
        for(int i=1;i<=2*T;i+=2)
        {
            scanf("%lld",&nums[i]);
        }
        bool mark=true;
        for(long long int a=0;a<MOD;a++)
        {
            long long int t=(ll)(nums[3]-a*a*nums[1]);
            long long int g;
            long long int b,k;
            ex_gcd(a+1,MOD,g,b,k);
            if(t%g)
                continue;
            b=b*(t/g);
            mark=true;
            for(int i=2;i<=2*T;i=i+2)
            {
                nums[i]=(a*nums[i-1]+b)%MOD;
                int temp=(a*nums[i]+b)%MOD;
                if(i<2*T&&temp!=nums[i+1])
                {
                    mark=false;
                    break;
                }
            }
            if(mark)
                break;
        }
        for(int i=2;i<=2*T;i=i+2)
            printf("%lld\n",nums[i]);
    }
    return 0;
}

ps.好久不写代码感觉脑子不行了,写了好多bug==

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注