来自 编程应用 2019-09-04 19:47 的文章
当前位置: 六合联盟网 > 编程应用 > 正文

高速幂乘,乘法逆元

Problem Description

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).

Considera positive integer X,and let S be the sum of all positive integer divisors of2004^X. Your job is to determine S modulo 29 (the rest of the division of S by29).

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.

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 29is equal to 6.

InputThe input consists of several test cases. Each test case contains a line with the integer X (1 <= X <= 10000000).

Input

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

Theinput consists of several test cases. Each test case contains a line with theinteger X (1 <= X <= 10000000).

1
10000
0

A test case of X = 0 indicates the end of input, and should not be processed.

Sample Output

Output

6
10

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

唯一分解定理:

Sample Input

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

1

约数和公式

10000

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

0

等比数列求和公式

Sample Output

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

6

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

10

 对于此题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。

除数和函数 :F(n) 求n的约数的和 ( 约数大于等于1 小于n )

取模不可用除法,所以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("%lldn",res*rev%mod);
    }
}

除数和函数是一个积性函数,满足性质 :当m , n 互质时, f(m*n) = f(m) * f(n)

  

如果 p 是一个素数,则 f(p^n) = 1 + p + p^2 +p^3 +p^4 + .... + p^(n-1) + p^n = (p^(n+1) -1)/p-1 (等比数列求和)

则题目中 f(2004^n) = f(2^(2*n)) * f(3^n) * f(167^n)

= (2^(2*n+1) -1) * (3^(n+1) -1)/2 *(167^(n+1) -1)/166

用到乘法逆元:(同余性质)

a^k/d = a^k*(d-1) d-1 即为d的逆元。 3的逆元为15 167 的逆元为18

具体参考:

然后还要用到 快速幂模:转换为位运算,这题要用这个,一般的会超时,具体看代码吧。

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

Code:

#include
using namespace std;
int Mod(int a,int b)//  快速幂模函数
{
    int t = 1;
    while(b)
    {
        if(b&1)
            t = t*a%29;
        b>>=1;
        a = a*a%29;
    }
    return t;
}
int main()
{

    int n,a,b,c;
    while(scanf("%d",&n)&&n)
    {
        a=(Mod(2,2*n+1)-1);
        b=(Mod(3,n+1)-1)*15;
        c=(Mod(22,n+1)-1)*18;
        printf("%dn",a*b*c%29);
    }
    return 0;
}

Description Considera positive integer X,and let S be the sum of all positive integer divisors of2004^X. Your job is to determine S modulo 29 (the rest of the division of S...

本文由六合联盟网发布于编程应用,转载请注明出处:高速幂乘,乘法逆元

关键词: