hdu_1452_Happy 2004 (乘法逆元

2018-06-17 21:34:33来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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.

InputThe 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.
OutputFor each test case, in a separate line, please output the result of S modulo 29.
Sample Input

1
10000
0

Sample Output

6
10

唯一分解定理:

  一个整数A一定能被分成:A=(P1^K1)*(P2^K2)*(P3^K3).....*(Pn^Kn)的形式。其中Pn为素数。

约数和公式

  对于一个已经被分解的整数A=(P1^K1)*(P2^K2)*(P3^K3).....*(Pn^Kn),有约数和S=(1+P1+P12+P13+.....P1k1)*.....(1+Pn+Pn2+Pn3+.....Pnkn)。

等比数列求和公式

  SUM=P1(1- P1^n)/(1-P1)=P1(P1^n  -1)/(P1-1)

S=SUM1+SUM2+......+SUMn

 对于此题ans=2^(2n+1)-1+(3^(n+1)-1)/2+(167^(n-1)-1)/166

乘法逆元:

  如果ax≡1 (mod p),且gcd(a,p)=1(a与p互质),则称a关于模p的乘法逆元为x。

扩展欧几里得在这里就不多说了。这里说一下费马小定理:

  假如a是整数,p为素数,则a^p-a为p的倍数。  由此可得a^p   - a=1 mod p  =>a^p=a mod p  =>a^(p-1) =1 mod p,结合逆元的定义,a*x=1 mod p。则逆元x=a^(p-2) mod p。

取模不可用除法,所以ans*乘法逆元,剩下的就是求出逆元可解。乘法逆元可由扩展欧几里得算法求得,也可有费马小定理求得。
  欧拉定理求逆元:a^(phi(m)-1);

代码如下:
#include<iostream>
#include<cstdio>
#define LL long long
#define mod 29
using namespace std;
LL pow(LL a,LL n)
{
    LL base=a,ret=1;
    while(n)
    {
        if(n&1) ret=(ret*base)%mod;
        base=(base*base)%mod;
        n>>=1;
    }
    return ret%mod;
}
int main()
{
    
    LL T,x;
    while(~scanf("%lld",&x),x)
    {
        LL rev=pow(13,27);//逆元
        LL res=(pow(2,2*x+1)-1)*(pow(3,x+1)-1)*(pow(22,x+1)-1);
        printf("%lld\n",res*rev%mod);
    }
}

  



标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:基于数组实现双端栈

下一篇:poj_1284_Primitive root