hdu5478 Can you find it+快速幂

Bertha 。 2022-07-15 00:26 144阅读 0赞

hdu5478 Can you find it+快速幂 题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=5478][http_acm.hdu.edu.cn_showproblem.php_pid_5478]

题面描述：

# Can you find it #

**Time Limit: 8000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)  
Total Submission(s): 1492 Accepted Submission(s): 614**

Problem 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

Source

[2015 ACM/ICPC Asia Regional Shanghai Online][2015 ACM_ICPC Asia Regional Shanghai Online]

题目大意：

求所有的数对（a，b），使得其满足题目中的公式，但是此题的简单之处就在于，只需要当n=1,2时满足题意即可。

具体解题思路（转）：

给你C,k1,k2,b1，按字典序输出满足![20150926203959507][]的所有(a,b)对

解题思路：因为![20150926203959507][]对于任意n均满足，故n=1的情况也是符合的，故可得

![20150926204413122][]①

而n=2的情况也是符合的，可得

![20150926210119422][]②

因为①式mod C = 0 ,所以①式乘以一个数mod C 仍为0，不妨①式\*![20150926210407958][]，可得

![20150926211621709][]

所以，我们只需遍历一遍a的取值(1~C-1)，利用快速幂计算出![20150926210407958][]，以及![20150926212225761][]，再根据式①可以算出b，再用一次快速幂求出![20150926212341071][]，比较![20150926210407958][](mod C)是否等于![20150926212341071][](mod C)即可

代码实现：

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    long long quick_mod(long long a,long long b,long long m)
    {
        long long ans=1;
        while(b)
        {
            if(b&1)
            {
                ans=(ans*a)%m;
                b--;
            }
            b/=2;
            a=a*a%m;
        }
        return ans;
    }
    
    int main()
    {
        long long c;
        long long k1,b1,k2;
        int casenum=1;
        while(scanf("%lld%lld%lld%lld",&c,&k1,&b1,&k2)!=EOF)
        {
            int flag=0;
            long long b=0;
            long long ans1=0,ans2=0,ans3=0;
            printf("Case #%d:\n",casenum++);
            for(long long i=1; i<c; i++)
            {
                ans1=quick_mod(i,k1,c)%c;
                ans2=quick_mod(i,k1+b1,c)%c;
                b=c-ans2;
                ans3=quick_mod(b,k2,c)%c;
                if(ans1==ans3)
                {
                    flag=1;
                    printf("%lld %lld\n",i,b);//注意：字典序指的是所有数对的字典序
                }
            }
            if(flag==0)
            {
                printf("-1\n");
            }
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5478]: http://acm.hdu.edu.cn/showproblem.php?pid=5478
[2015 ACM_ICPC Asia Regional Shanghai Online]: http://acm.hdu.edu.cn/search.php?field=problem&key=2015+ACM%2FICPC+Asia+Regional+Shanghai+Online&source=1&searchmode=source
[20150926203959507]: /images/20220715/e990553e075c4d4e9efe4aa3e475adb4.png
[20150926204413122]: /images/20220715/f20386d6c67341b4852ab9373a8f3b6b.png
[20150926210119422]: /images/20220715/1bb88dc77d0e450e9714344a317b830a.png
[20150926210407958]: /images/20220715/b39930f4e0df41a5a13e9938dbe5b73b.png
[20150926211621709]: /images/20220715/2fe47238e6eb4fe0aec55b8c41301bd8.png
[20150926212225761]: https://img-blog.csdn.net/20150926212225761
[20150926212341071]: /images/20220715/62a905f94565450c8704bd25f83a5c74.png