HDU 5478 Can you find it 随机化数学

2023-07-25 08:33:46

Can you find it

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=5478

Description

Given a prime number C(1≤C≤2×105), and three integers k1, b1, k2 (1≤k1,k2,b1≤109). Please find all pairs (a, b) which satisfied the equation ak1⋅n+b1 + bk2⋅n−k2+1 = 0 (mod C)(n = 1, 2, 3, ...).

Input

There are multiple test cases (no more than 30). For each test, a single line contains four integers C, k1, b1, k2.

Output

First, please output "Case #k: ", k is the number of test case. See sample output for more detail.
Please output all pairs (a, b) in lexicographical order. (1≤a,b<C). If there is not a pair (a, b), please output -1.

Sample Input

23 1 1 2

Sample Output

Case #1:
1 22

HINT

题意

问你有多少对数，满足a^(k1⋅n+b1) + b^(k2⋅n−k2+1) = 0 (mod C)

题解：

首先你要知道，对于每个a只有唯一对应的b可以满足这个式子，因为当n=1的时候，a^(k1+b1)+b = kk*C

由于b是小于c的，所以只有一个

所以我们可以求出b来，然后我们怎么check这个b究竟是不是呢？

随机化10个数，然后随便check就好了

代码：

//qscqesze

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <bitset>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 100006

#define mod 1000000007

#define eps 1e-9

#define e exp(1.0)

#define PI acos(-1)

const double EP  = 1E- ;

int Num;

//const int inf=0x7fffffff;

const ll inf=;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//*************************************************************************************

ll fMul(int m,ll n,int k)

{

    ll cc = m;

    ll b = ;

    while (n > )

    {

          if (n & 1LL)

            {

                b = (b*cc);

                if(b>=k)

                    b%=k;

            }

          n = n >> 1LL ;

          cc = (cc*cc)%k;

          if(cc>=k)cc%=k;

    }

    return b;

}

int main()

{

    //freopen("out.txt","r",stdin);

    //freopen("out2.txt","w",stdout);

    srand(time(NULL));

    int tot = ;

    int c ,k1 ,b1 ,k2;

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

    {

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

        int flag1 = ;

        for(int i=;i<c;i++)

        {

            int j=c-fMul(i,k1*+b1,c);

            int flag = ;

            for(int k=;k<=;k++)

            {

                ll tt = rand()%c+;

                ll ttt1 = k1, ttt2 = k2,ttt3 = b1;

                if((fMul(i,ttt1*tt+ttt3,c)+fMul(j,ttt2*tt-ttt2+1LL,c))%c!=)

                {

                    flag = ;

                    break;

                }

            }

            if(flag)

            {

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

                flag1=;

            }

        }

        if(!flag1)

            printf("-1\n");

    }

}

码农公寓