HDU 5478 Can you find it(数学问题)

题目大意：

给你  ak1⋅n+b1+ bk2⋅n−k2+1 = 0 (mod C)(n = 1, 2, 3, ...). 要求所有的n都满足上述的式子。

问这样的a,b 有多少对？

 

分析这个问题的时候需要补充一下余数的性质定理。

 

• 若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；
• 若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；
• 若a≡b (% p)，c≡d (% p)，
  则 (a + c) ≡ (b + d) (%p)，
       (a - c) ≡ (b - d) (%p)，
       (a * c) ≡ (b * d) (%p)，
       (a / c) ≡ (b / d) (%p)；
   
  ===============================================================================
  n = 1  ........................   a^(k1+b1) + b  = 0(Mod C)  ①
  n = 2 .........................   a^(2*k1+b1) + b^(k2+1) = 0 (Mod C)  ②
  设 ①*a^k1 .................................. a(2*k1+b1) + a^k1*b = 0(Mod C)  ③ 
• 根据式子  ② 和 ③ 得：

          a^(2*k1+b1) + b^(k2+1) <=> a(2*k1+b1) + a^k1*b

          化简后：  b^k2 <=> a^k1

所以经过上面式子的证明，可以得知，我们只要前两项Mod C == 0 那么 这个a和b就是符合的。

 

 

=======================================================================================================

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const LL INF = 0xffffff;
const LL maxn = 100005;
const LL MOD = 1e9+7;
LL C, k1, k2, b1;

LL QuickPow(LL a, LL k, LL mod)
{
    LL ans = 1, P = a;
    while( k )
    {
        if(k%2 == 1)
            ans = (ans * P)%mod;
        k /= 2;
        P = (P * P)%mod;
    }
    return ans;
}

int main()
{
    LL ans = 0, a, b;
    int cas = 1;

    while(cin >> C >> k1 >> b1 >> k2)
    {
        ans = 0;
        printf("Case #%d:
", cas ++);

        for(int i=1; i<C; i++)///枚举a
        {
            a = i;
            b = C - QuickPow(a, k1+b1, C);
            if( (QuickPow(a, 2*k1+b1, C) + QuickPow(b, k2+1, C))%C == 0 )
            {
                printf("%I64d %I64d
", a, b);
                ans ++;
            }

        }
        if(ans == 0)
            printf("-1
");
    }
    return 0;
}