hdu 5478 （数论）

题意：给定 C，k1, b1, k2 找出所有的（a, b）满足 ak1⋅n+b1+ bk2⋅n−k2+1 = 0 (mod C)(n = 1, 2, 3, ...) （1<=a, b <C）

1. 当n = 1时， a^(k1+b1) + b = 0 ( mod C) => a^(2 * k1+b1) + b*a^(k1) = 0 ( mod C) ①

当n = 2时， a^(2 * k1 + b1) + b^(k2 + 1) = 0 (mod C) ②

所以 ① ，②结合可以推出 b^(k2) = a^(k1)

所以求出 a ，b再判断是否符合本式即可

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

typedef long long ll;

ll pow_mod(int a,int n,int mod)

{

    if(n == 0)

        return 1;

    ll x = pow_mod(a,n/2,mod);

    ll ans = (ll)x*x%mod;

    if(n %2 == 1)

        ans = ans *a % mod;

    return ans;

}

int main()

{

    int b1,k1,k2,mod;

    int cas = 1;

    while(scanf("%d%d%d%d",&mod,&k1,&b1,&k2) != EOF)

    {

        bool flag = false;

        printf("Case #%d:\n",cas++);

        for(int i = 1; i < mod; i++)

        {

            ll tmp = pow_mod(i,k1+b1,mod);

            int b = mod - tmp;

            ll tta = pow_mod(i,k1,mod);

            ll ttb = pow_mod(b,k2,mod);

            if(tta == ttb)

            {

                flag = true;

                printf("%d %d\n",i,b);

            }

        }

        if(!flag)

            printf("-1\n");

    }

    return 0;

}

2.

求出1 - c所有的a ，b 的情况，再枚举n进行判断，但感觉不是很靠谱- -

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

typedef long long ll;

ll pow_mod(ll a,ll n,ll mod)

{

    if(n == 0)

        return 1;

    ll x = pow_mod(a,n/2,mod);

    ll ans = (ll)x*x%mod;

    if(n %2 == 1)

        ans = ans *a % mod;

    return ans;

}

int main()

{

    ll b1,k1,k2;

    ll mod;

    int cas = 1;

    while(scanf("%I64d%I64d%I64d%I64d",&mod,&k1,&b1,&k2) != EOF)

    {

        bool flag = true;

        int ok;

        printf("Case #%d:\n",cas++);

        for(ll i = 1; i < mod; i++)

        {

            ll temp = pow_mod(i,k1+b1,mod);

            ll b = (temp/mod + 1)*mod - temp;

            ok = 1;

            for(ll j = 2; j <= 100; j++)

            {

                ll ans1 = pow_mod(i, k1 * j + b1, mod);

                ll ans2 = pow_mod(b, k2 * j - k2 + 1, mod);

                ll ans = (ans1+ans2)%mod;

                if(ans)

                {

                    ok = 0;

                    break;

                }

            }

            if(ok)

            {

                flag = 0;

                printf("%I64d %I64d\n",i,b);

            }

        }

        if(flag)

            printf("-1\n");

    }

    return 0;

}

巴特西

hdu 5478 （数论）

最新文章

热门文章