POJ 1845-Sumdiv(快速幂取模 整数唯一分解定理 约数

2019-11-15 作者:计算机教程   |   浏览(94)

POJ 1845-Sumdiv(快速幂取模 整数唯一分解定理 约数和公式 同余模公式)

 

Sumdiv Time Limit:1000MS Memory Limit:30000KB 64bit IO Format:%I64d & %I64u Submit Status Practice POJ 1845 Appoint description: System Crawler (2015-05-27)

Description

Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).

Input

The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.

Output

The only line of the output will contain S modulo 9901.

Sample Input

2 3

Sample Output

15

Hint

2^3 = 8.
The natural divisors of 8 are: 1,2,4,8. Their sum is 15.
15 modulo 9901 is 15 (that should be output).

题意:求(A^B)的约数和对9901取余的结果。

 

思路:转载--->優YoU

 

解题思路:

要求有较强 数学思维 的题

应用定理主要有三个:

要求有较强 数学思维 的题

应用定理主要有三个:

(1) 整数的唯一分解定理:

任意正整数都有且只有一种方式写出其素因子的乘积表达式。

A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn) 其中pi均为素数

(2) 约数和公式:

对于已经分解的整数A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)

有A的所有因子之和为

S = (1 p1 p1^2 p1^3 ...p1^k1) * (1 p2 p2^2 p2^3 ….p2^k2) * (1 p3 p3^3 … p3^k3) * .... * (1 pn pn^2 pn^3 ...pn^kn)

(3) 同余模公式:

(a b)%m=(a%m b%m)%m

(a*b)%m=(a%m*b%m)%m

 

有了上面的数学基础,那么本题解法就很简单了:

1: 对A进行素因子分解

分解A的方法:

A首先对第一个素数2不断取模,A%2==0时 ,记录2出现的次数 1,A/=2;

当A%2!=0时,则A对下一个连续素数3不断取模...

以此类推,直到A==1为止。

 

注意特殊判定,当A本身就是素数时,无法分解,它自己就是其本身的素数分解式。

 

最后得到A = p1^k1 * p2^k2 * p3^k3 *...* pn^kn.
故 A^B = p1^(k1*B) * p2^(k2*B) *...* pn^(kn*B);

2:A^B的所有约数之和为:

sum = [1 p1 p1^2 ... p1^(a1*B)] * [1 p2 p2^2 ... p2^(a2*B)] *...* [1 pn pn^2 ... pn^(an*B)]永利电子游戏网站,.

3: 用递归二分求等比数列1 pi pi^2 pi^3 ... pi^n:

(1)若n为奇数,一共有偶数项,则:
1 p p^2 p^3 ... p^n

= (1 p^(n/2 1)) p * (1 p^(n/2 1)) ... p^(n/2) * (1 p^(n/2 1))
= (1 p p^2 ... p^(n/2)) * (1 p^(n/2 1))

上式红色加粗的前半部分恰好就是原式的一半,那么只需要不断递归二分求和就可以了,后半部分为幂次式,将在下面第4点讲述计算方法。

 

(2)若n为偶数,一共有奇数项,则:
1 p p^2 p^3 ... p^n

= (1 p^(n/2 1)) p * (1 p^(n/2 1)) ... p^(n/2-1) * (1 p^(n/2 1)) p^(n/2)
= (1 p p^2 ... p^(n/2-1)) * (1 p^(n/2 1)) p^(n/2);

上式红色加粗的前半部分恰好就是原式的一半,依然递归求解

 

4:反复平方法计算幂次式p^n

这是本题关键所在,求n次幂方法的好坏,决定了本题是否TLE。

以p=2,n=8为例

常规是通过连乘法求幂,即2^8=2*2*2*2*2*2*2*2

这样做的要做8次乘法

 

而反复平方法则不同,

定义幂sq=1,再检查n是否大于0,

While,循环过程若发现n为奇数,则把此时的p值乘到sq

{

n=8>0 ,把p自乘一次, p=p*p=4 ,n取半 n=4

n=4>0 ,再把p自乘一次, p=p*p=16 ,n取半 n=2

n=2>0 ,再把p自乘一次, p=p*p=256 ,n取半 n=1,sq=sq*p

n=1>0 ,再把p自乘一次, p=p*p=256^2 ,n取半 n=0,弹出循环

}

则sq=256就是所求,显然反复平方法只做了3次乘法

 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
using namespace std;
typedef long long LL;
const int inf=0x3f3f3f3f;
const double eps=1e-10;
const double pi= acos(-1.0);
const int MAXN=1e5 10;
const int mod=9901;
LL Mul(LL a,LL b) {//快速乘法
    LL res=0;
    while(b>0) {
        if(b&1) res=(res a)%mod;
        b>>=1;
        a=(a a)%mod;
    }
    return res;
}
LL modxp(LL a,LL b) {//快速幂取余
    LL res=1;
    while(b>0) {
        if(b&1) res=Mul(res,a);
        b>>=1;
        a=Mul(a,a);
    }
    return res;
}
LL Sum(LL p,LL n) {//递归二分求 (1   p   p^2   p^3  ...  p^n)%mod  
    if(n==0)
        return 1;
    if(n&1)
        return ((1 modxp(p,n/2 1))%mod*Sum(p,n/2)%mod)%mod;
    else
        return ((1 modxp(p,n/2 1))%mod*Sum(p,(n-1)/2)%mod modxp(p,n/2)%mod)%mod;
}

int main() {
    int A,B,i;
    int p[MAXN];//A的分解式p[i]^k[i];
    int k[MAXN];
    while(~scanf("%d %d",&A,&B)) {
        int cnt=0;
        for(i=2; i*i<=A; i  ) {//分解整数A (A为非质数)
            if(A%i==0) {
                p[cnt]=i;
                k[cnt]=0;
                while(A%i==0) {
                    A/=i;
                    k[cnt]  ;
                }
                cnt  ;
            }
        }
        if(A!=1) {//特殊判定:分解整数A (A为质数)
            p[cnt]=A;
            k[cnt]=1;
            cnt  ;
        }
        int res=1;
        for(i=0; i 

http://www.bkjia.com/cjjc/1009458.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1009458.htmlTechArticlePOJ 1845-Sumdiv(快速幂取模 整数唯一分解定理 约数和公式 同余模公式) Sumdiv Time Limit: 1000MS Memory Limit: 30000KB 64bit IO Format: %I64d %I64u Submit Status...

POJ 1845 Sumdiv (因子和)

Sumdiv

Time Limit: 1000MS   Memory Limit: 30000K
Total Submissions: 15404   Accepted: 3800

Description

Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).

Input

The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.

Output

The only line of the output will contain S modulo 9901.

Sample Input

2 3

Sample Output

15

这个题和HDU的1452基本上一样,只不过这里是HDU的推广。
先说这个题的解题步骤: ① 将A分解A=(p1^a1)*(p2^a2)*.....*(pk^ak),那么A^B就是A^B=[p1^(a1*B)] * [p2^(a2*B)] *.....*[pk^(ak*B)] ② 根据约数和的公式求和S并mod9901 别急,下面还有一些细节问题:
这个题我一开始就是先分解,然后按约数和的公式算.但是一直WA,我改了许多地方都不行。 如果一个数n=(p1^a1)*(p2^a2)*.....*(pk^ak) 约数和s=(p1^(a1 1)-1)/(p1-1) * (p2^(a2 1)-1)/(p2-1) *.....* (pk^(ak 1)-1)/(pk-1) 我就是按这个求s的公式算的,但是一直不对,肯定是因为这个公式中涉及到了除法,虽然在模运算中出现除法可以借助逆元来解决,但是因为求逆元是有条件限制的(a在模m意义下存在逆元的充要条件是a和m互素),我想是肯定是在处理这个地方的时候一直没处理好,所以一直WA。
其实是我忽略了另一个公式,我上面给的求s公式是变形之后的,变形之前是: s=(1 p1 p1^2 p1^3 ...p1^a1) * (1 p2 p2^2 p2^3 ….p2^a2) * (1 p3 p3^3 … p3^a3) * .... * (1 pk pk^2 pk^3 ...pk^ak) 这个公式是不涉及除法的,用起来会很舒服。(而对这个公式每个括号里都是一个等比数列,分别对其求和就是上面的那个带除法的公式)。 至此问题就明了了。
那么就抛开这个题看下面的知识: 类似于这样的一个问题:S(k)=A^0 A^1 A^2 .... A^k的快速求和。 方法:二分 递归求解。 下面看个简单例子: ① k=4为偶数 A^0 A^1 A^2 A^3 A^4 =(A^0 A^1) A^2 A^3(A^0 A^1)=(1 A^3)*[A^0 A^1] A^2=(1 A^(k/2 1))*S(k/2-1) A^(n/2) ② k=5为奇数 A^0 A^1 A^2

  • A^3 A^4 A^5
    =[A^0 A^1 A^2] A^3*[A^0 A^1 A^2] = (1 A^3)*[A^0 A^1
  • A^2] = (1 A^(k/2 1))*S(k/2) 上面式子中,蓝色部分用快速幂,红色部分继续递归,这样就可以快速求出S(k)了。 递归出口n==0 return 1;
    代码中divi[i][0]代表第i个素因子,divi[i][0]代表这个素数的次数。

    #include #include #include #include using namespace std; typedef __int64 ll;

    const int MOD=9901; ll divi[10000][2],tot;

    ll quick_mod(ll a,ll b){ //a^b%MOD ll res=1; a%=MOD; while(b){

    if(b&1) res=(res*a)%MOD;
    b/=2;
    a=(a*a)%MOD;
    

    } return res; }

    ll cal(int p,int n){ if(n==0) return 1; if(n&1)

    return (1 quick_mod(p,n/2 1))*cal(p,n/2)%MOD;
    

    else

    return ((1 quick_mod(p,n/2 1))*cal(p,n/2-1) quick_mod(p,n/2))%MOD;
    

    }

    void pre_solve(ll n){ ll i; tot=0; for(i=2;i*i<=n;){

    if(n%i==0){
     divi[tot][0]=i;
     divi[tot][1]=0;
     do{
      n/=i;divi[tot][1]  ;
     }while(n%i==0);
     tot  ;
    }
    if(i==2) i  ;
    else i =2;
    

    } if(n>1){

    divi[tot][0]=n;divi[tot][1]=1;tot  ;
    

    } }

    int main() { ll A,B,i,res; while(scanf("%I64d%I64d",&A,&B)!=EOF){

    if(A==0){   //别忘了特判
     printf("0n");continue;
    }
    if(A==1 || B==0){
     printf("1n");continue;
    }
    pre_solve(A);
    res=1;
    for(i=0;i
    

http://www.bkjia.com/cjjc/990697.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/990697.htmlTechArticlePOJ 1845 Sumdiv (因子和) Sumdiv Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 15404 Accepted: 3800 Description Consider two natural numbers A and B. Let S be th...

本文由永利电子游戏网站发布于计算机教程,转载请注明出处:POJ 1845-Sumdiv(快速幂取模 整数唯一分解定理 约数

关键词: