因子和

題目描述

輸入兩個整數 a和 b，求 a b a^b ab的因子和，

由于結果太大，只要輸出它對 9901 取模的結果，

輸入格式

僅一行，為兩個整數 a 和 b，

輸出格式

輸出一行一個整數表示答案對 9901 取模的結果，

輸入

2 3

輸出

15

資料規模與約定

對于全部的測驗點，保證保證 0≤b≤5×10^7 ，

首先我們了解一下因子和咋求：

百度百科：算識訓本定理，又稱為正整數的唯一分解定理,即:每個大于1的自然數均可寫為質數的積,而且這些素因子按大小排列之后,寫法僅有一種方式，

即任何大于1的整數n可以唯一的表示成

n= p 1 a 1 {p_1}^{a_1} p1?a1? p 2 a 2 {p_2}^{a_2} p2?a2? p 3 a 3 {p_3}^{a_3} p3?a3? p 4 a 4 {p_4}^{a_4} p4?a4?… p n a n {p_n}^{a_n} pn?an?

其因子和為： ( p 1 0 + p 1 1 + p 1 2 . . . . . (p_1^0+p_1^1+p_1^2..... (p10?+p11?+p12?..... p 1 a 1 ) {p_1}^{a_1}) p1?a1?) ( p 2 0 + P 2 1 + p 2 2 . . . . . (p_2^0+P_2^1+p_2^2..... (p20?+P21?+p22?..... p 2 a 2 ) {p_2}^{a_2}) p2?a2?)… ( p n 0 + p n 1 + p n 2 . . . . . (p_n^0+p_n^1+p_n^2..... (pn0?+pn1?+pn2?..... p n a n ) {p_n}^{a_n}) pn?an?)

= ∏ i = 0 n \prod \limits_{i=0}^n i=0∏n? P i a i + 1 ? 1 p i ? 1 \frac{{P_i}^{a_i+1}-1}{{p_i}-1} pi??1Pi?ai?+1?1?怎么來的我不知道哈，請移步度娘，

然后怎么做嘞：（本題參考了洛谷題解，所以思路可以有點相似哦）

1：先把質因子，和他的冪次分解出來，用兩個陣列保存

? 舉一個桃子吧，假如給定一個數字100;首先我們從第一個質數2開始

? 100%2==0 ，100/2=50，現在我們記錄了2這個數字，冪次為1.

? 50%2==0,50/2=25 質因子2的冪次加一為2;

? 25%2!=0; i++;一直到下一個能被整除的，

? 25%5==0 25/5=5;現在記錄5這個數字，冪次為1

? 5%5==0 5/5=1質因子2的冪次加一為2,最終我們得到100分解為因子是 2 2 5 5 ，

2：利用保存的質因子及其冪次，連乘（哦對，中間求逆元的時候還有一個坑，當 p i p_i pi?是質數但是 ( p i ? 1 ) (p_i - 1) (pi??1)的值是取模值的倍數的時候，就不能直接用逆元了，但是 p i % m o d p_i \% mod pi?%mod目前是等于1啊，也不復雜，即 ( 1 + p i 1 + p i 2 + ? + p i a i ) % P (1+ p_i ^1+p_i^{2}+\cdots+p_i^{a_i})\%P (1+pi1?+pi2?+?+piai??)%P= ( 1 + 1 + 1 + ? + 1 ) (1+1+1+\cdots+1) (1+1+1+?+1)= a i + 1 a_i+1 ai?+1

還有就是，，，取模，，記得取模，，必須取模，，永遠取模，，好了，散了，自己動動手吧~

完整代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 9901
int a,b,zyz[10000],mc[10000],num=0;//zyz是質因子，mc對應著冪次，num記錄有多少個不同的質因子相乘
ll ans=1;//最后結果 

//快讀模板 
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f; 
}
//快速冪（用于費馬小定理求逆元）
ll fastpow(ll x,ll y)
{
	x%=mod;
	ll res=1;
	while(y)
	{
		if(y&1) res=res%mod*x%mod;
		y>>=1;
		x=x*x%mod;
	}
	return res%mod;
}

//連乘中每一項的值 x為質因數，y為對應質因數的冪次  
int solve(int x,int y)
{
	int k=0;y=y*b;//每一個質因子的冪次都還要乘以原題中的指數的大小 
	//特判分母和模數不互質的情況 
	if((x-1)%mod==0) k=(y+1)%mod; 
	else k=(fastpow(x%mod,y+1)-1)%mod*fastpow((x-1)%mod,mod-2)%mod;
	return k%mod; 
} 

int main()
{
	a=read();b=read();
	//底數分解質因子，求其冪次  
	for(int i=2;i*i<=a;i++){
		if(a%i==0)
		{
			num++;
			zyz[num]=i;
			mc[num]=1;
			a/=i;
			while(a%i==0)//還可以繼續被這個質因子整除
		    {
		    	mc[num]++;
		    	a/=i; 
		    } 
		}
	}
	if(a!=1)//可能剩余一個很大的質因子數
	{
		num++;
		zyz[num]=a;
		mc[num]=1; 
	} 
	
	//連乘
	for(int i=1;i<=num;i++)
	{
		ans=ans*solve(zyz[i],mc[i])%mod;
	}
	printf("%d\n",(ans%mod+mod)%mod);
	return 0; 
}
 
 

是不是非常友好嘞，覺得友好請來一個友好的贊，覺得不友好的，wa我都wawawawawawawawawawawawawa了卑微(bushi)