hdu-1452(约数和定理+求逆元)

ゝ一世哀愁。 2022-06-09 01:21 156阅读 0赞

问题描述:

Consider a positive integer X,and let S be the sum of all positive integer divisors of 2004^X. Your job is to determine S modulo 29 (the rest of the division of S by 29).   
  
Take X = 1 for an example. The positive integer divisors of 2004^1 are 1, 2, 3, 4, 6, 12, 167, 334, 501, 668, 1002 and 2004. Therefore S = 4704 and S modulo 29 is equal to 6.

Input

The input consists of several test cases. Each test case contains a line with the integer X (1 <= X <= 10000000).   
  
A test case of X = 0 indicates the end of input, and should not be processed.

Output

For each test case, in a separate line, please output the result of S modulo 29.

Sample Input

1
    10000
    0

Sample Output

6
    10

题目题意:题目给我们一个让我们求出2004^x的所有的约数和，然后%29.

题目分析:这个题目就是考到了一个定理(约数和定理),数论的题目考的范围很广（定理很多，所以得多做题目，多总结),下面是百度对约数和定理的解释。

对于一个大于1正整数n可以[分解质因数][Link 1]：n=p1^a1\*p2^a2\*p3^a3\*…\*pk^ak,

则由[约数个数定理][Link 2]可知n的正约数有(a₁+1)(a₂+1)(a₃+1)…(ak+1)个

那么n的(a₁+1)(a₂+1)(a₃+1)…(ak+1)个正约数的和为

f(n)=(p1^0+p1^1+p1^2+…p1^a1)(p2^0+p2^1+p2^2+…p2^a2)…(pk^0+pk^1+pk^2+…pk^ak）。

知道到了这个定理，是不是就明了了。

2004=2^2\*3\*167

则2004^x=2^(2\*x)\*3^(x)\*167^(x).

我们由公式展开:

f(x)=(2^0+2^1+2^2+2^3+.....+2^(2\*x))\*(3^0+3^1+3^2+3^3+....+3^x)\*(167^0+167^1+167^2+167^3+.........+167^x)

又等比公式求和公式可以化简得:

f(x)=(2^(2\*x+1)-1)\*(3^(x+1)-1)\*(167^(x+1)-1)/332%29.

存在除法取余，那么肯定得求逆元。

一开始我用了费马小定理，错了！！！是自己没有注意各种求逆元方法范围，下面写了各种求逆元方法和范围。

对于同于方程ax=1 mod m 当gcd(a,m)==1时那么肯定存在x等于1/a  mod m即x 就是a在模数为m下的逆元.

方法一:扩展欧几里得法:

我们对同余方程ax=1 mod m

即ax +my=1 求解这个同余方程即可。

方法二:费马小定理:

假如p是[质数][Link 3]，且gcd(a,p)=1，那么 a(p-1)≡1（mod p）

我们变形:即a\*a^(p-2)=1 mod p 那么a^(p-2)=1 /a mod p

即a^(p-2) 为逆元，注意p要是质数

方法三:欧拉定理法:

在 [数论][Link 4]中，欧拉定理,（也称 [费马][Link 5]\-欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为 [正整数][Link 6]，且n,a [互质][Link 7]，则: ![0823dd54564e92584b7cba389d82d158cdbf4e9f.jpg][]

我们变形:即a^(phi(n)-1)= 1 /a mod n 为逆元。

方法四:线形打表求逆元

当模数p为质数时:

Inv\[i\]=inv\[mod%i\]\*(mod-mod/i)%mod; (其中inv\[i\]保存的是i的逆元,复杂度为o(n)),证明可以百度搜一下.

好了，我知道的就这么多了。

这道题目的代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    
    const int mod=29;
    
    int exgcd(int a,int b,int &x,int &y)
    {
        if (b==0) {
            x=1;
            y=0;
            return a;
        }
        int r=exgcd(b,a%b,x,y);
        int t=x;
        x=y;
        y=t-a/b*y;
        return r;
    }
    bool linear_equation(int a,int b,int c,int &x,int &y)
    {
        int d=exgcd(a,b,x,y);
        if (c%d)
            return false;
        int k=c/d;
        int t=b/d;
        x=x*k,y=y*k;
        x=(x%t+t)%t;
        return true;
    }
    int fast_pow(int base,int k)
    {
        int ans=1;
        while (k) {
            if (k&1)
                ans=ans*base%mod;
            base=base*base%mod;
            k>>=1;
        }
        return ans;
    }
    int main()
    {
        int x,inv,k1,k2;
        linear_equation(332,mod,1,k1,k2);//扩展欧几里得，求逆元
        inv=k1;
        while (scanf("%d",&x)!=EOF) {
            if (x==0) break;
            int ans=1;
            ans=ans*(fast_pow(2,2*x+1)-1)%mod;
            ans=ans*(fast_pow(3,x+1)-1)%mod;
            ans=ans*(fast_pow(167,x+1)-1)%mod;
            ans=ans*inv%mod;
            printf("%d\n",ans);
        }
        return 0;
    }

[Link 1]: https://baike.baidu.com/item/%E5%88%86%E8%A7%A3%E8%B4%A8%E5%9B%A0%E6%95%B0
[Link 2]: https://baike.baidu.com/item/%E7%BA%A6%E6%95%B0%E4%B8%AA%E6%95%B0%E5%AE%9A%E7%90%86
[Link 3]: https://baike.baidu.com/item/%E8%B4%A8%E6%95%B0
[Link 4]: https://baike.baidu.com/item/%E6%95%B0%E8%AE%BA
[Link 5]: https://baike.baidu.com/item/%E8%B4%B9%E9%A9%AC
[Link 6]: https://baike.baidu.com/item/%E6%AD%A3%E6%95%B4%E6%95%B0
[Link 7]: https://baike.baidu.com/item/%E4%BA%92%E8%B4%A8
[0823dd54564e92584b7cba389d82d158cdbf4e9f.jpg]: https://gss2.bdstatic.com/9fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D116/sign=b4a8aa2a7dd98d1072d40830173eb807/0823dd54564e92584b7cba389d82d158cdbf4e9f.jpg