宝塔服务器面板，一键全能部署及管理，送你10850元礼包，点我领取

本篇内容介绍了“Java高次幂取模+积性函数+逆元的方法”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

题目意思：2004^x的所有正因数的和S)对29求余；输出结果；

原题链接

题目解析：解析参照来源：点击打开链接

因子和

6的因子是1,2,3,6; 6的因子和是s6)=1+2+3+6=12;

20的因子是1,2,4,5,10,20; 20的因子和是s20)=1+2+4+5+10+20=42;

2的因子是1,2; 2的因子和是s2)=1+2=3;

3的因子是1,3; 3的因子和是s3)=1+3=4;

4的因子和是
s4)=1+2+4=7;

5的因子和是
s5)=1+5=6;

s6)=s2)*s3)=3*4=12;

s20)=s4)*s5)=7*6=42;

这是巧合吗？

再看 s50)=1+2+5+10+25+50=93=3*31=s2)*s25),s25)=1+5+25=31.

这在数论中叫积性函数，当gcda,b)=1时sa*b)=sa)*sb);

如果p是素数

sp^n)=1+p+p^2+…+p^n=p^n+1)-1) /p-1) 1)

例 hdu1452 Happy2004

计算 因子和 s2004^X) mod 29,

2004=2^2 *3 *167

s2004^X) ) = s2^2X))) *s3^X))) * s167^X)))

167)=22;

s2004^X) ) = s2^2X))) *s3^X))) * s22^X)))

a=s2^2X)=2^2X+1)-1)//根据 （1）

b=s3^X)= 3^X+1)-1)/2//根据 （1）

c=s22^X)= 22^X+1)-1)/21//根据 （1）

%运算法则
1. a*b) %p= a%p) *b%p)

%运算法则
2. a/b) %p= a *b^-1)%p)

b^-1)是
b的逆元素 （%p）

2的逆元素是15 （)） ，因为2*15=30 % 29=1 % 29

21的逆元素是18 （)） ，因为21*18=378% 29 =1 % 29

因此

a=（powi2,2*x+1,29)-1）%29;

b=powi3,x+1,29)-1)*15 %29;

c=powi22,x+1,29)-1)*18 %29;

ans=（a*b）% 29*c % 29;

资料拓展： 1.

高次幂快速取模链接
                          2.积性函数：在数论中的积性函数：对于正整数n的一个算术函数
fn)，若f1)=1，且当a,b互质时fab)=fa)fb)，在数论上就称它为积性函数。若
                                                       对于某积性函数 fn) ，就算a, b不互质，也有fab)=fa)fb)，则称它为完全积性的。若将n表示成质因子分解式;
                    3.求逆元：
                           
在计算a/b)%Mod时，往往需要先计算b%Mod的逆元p（b有逆元的条件是gcdb,Mod)==1，显然素数肯定有逆元），然后由a*p)%Mod      
  得结果c。这
 里b的逆元p满足b*p)%Mod=1。先来简单证明一下：
   a/b)%Mod=c;    b*p)%Mod=1;    ==》   a/b)*b*p) %Mod=c;    ==》    a*p)%Mod=c;

从上面可以看出结论的正确性，当然这里b需要是a的因子。接下来就需要知道根据b和Mod，我们怎么计算逆元p了。扩展欧几里德算法，大家应该都知道，就是已知a、b，求一组解x,y)使得a*x+b*y=1。这里求得的x即为a%b的逆元，y为b%a的逆元（想想为什么？把方程两边都模上b或a看看）。

下面解释原因：

模m乘法逆元

定义：对于整数a，m，如果存在整数b，满足ab ≡ 1mod m)，则说，b是a的模m乘法逆元。

定理：a存在模m的乘法逆元的充要条件是gcda,m) = 1

充分性：

因为

gcda,m) = 1

根据欧拉定理，有

a^φm) ≡ 1mod m)

因此

a * a^φm)-1) mod m = 1

所以存在a的模m乘法逆元，即a^φm)-1)

必要性：

假设存在a模m的乘法逆元为b，则

ab ≡ 1 mod m)

所以

ab = km +1

所以

1 = ab – km

由欧几里得定理，有

gcda,m) = 1

由定理知：

对于ax + by = 1，可以看出x是a模b的乘法逆元，y是b模a的乘法逆元。

反过来，要计算a模b的乘法逆元，就相当于求ax + by = 1的x的最小正整数解，从而化为线性不定方程解决。

具体参考：http://blog.csdn.net/synapse7/article/details/9901195调用ExtGcd（b,Mod,x,y)，x即为b%Mod的逆元p。 
  求b%Mod的逆元p还有另外一种方法，即p=b^Mod-2)%Mod，因为b^Mod-1)%Mod=1这里需要Mod为素数)。错误分析：1:ify&1)ans*=x%29;//误把试中ans=x*x%292.数据类型要用__int64,

代码实现：

#include<cstdio>
#include<cstdlib>
using namespace std;
typedef __int64 ll;
ll  powmolll  x,ll  y)//高次幂取模的求x^ymod29
{
    ll  ans=1;
    x=x%29;
    whiley)
    {
        ify&1)ans*=x%29;//y是奇数情况的处理；
        x=x*x%29;
        y>>=1;//
    }
    return ans;
}
int main)
{
    ll  x,a,b,c;
    whilescanf"%I64d",&x),x)
    {
        a=powmol2,2*x+1)-1)%29;
        b=powmol3,x+1)-1)*15%29;
        c=powmol22,x+1)-1)*18%29;
        printf"%I64d\n",a*b)%29*c%29);
    }
    return 0;
}