本文主要是介绍唯一分解定理小练，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
POJ 1845 Sumdiv
这是一道考查唯一分解定理的题目，提议是给出A和B，让你求出A^B的所有因数的和。由唯一分解定理可知。A^B=(x1^y1)*(x2^y2)*...*(xn^yn)，且其中x1,x2,,,xn均为质数。这样的话因数的和就可以知道为：(1+x1+x1^2+...+x1^y1)*(1+x2+x2^2+...+x2^y2)*...*(1+xn+xn^2+xn^yn)，这样的话又继续分析。发现(1+x+x^2+x^3)=(1+x)*(1+x^2);(1+x+x^2+x^3+x^4)=(1+x)*(1+x^3)+x^2;这样就可通过对奇偶进行判断递归得到相应的值了。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int ci[7100],ge[7100];
__int64 p(__int64 x,__int64 y)//求y次方
{__int64 res=1;while(y>0){if(y%2==1){res=(res*x)%9901;}x=(x*x)%9901;y/=2;}return res;
}
__int64 g(__int64 r,__int64 l)//递归求和
{if(l==0){return 1;}if(l%2==1){return ((1+p(r,l/2+1))%9901*g(r,l/2)%9901)%9901;}else{return ((1+p(r,l/2+1))%9901*g(r,l/2-1)%9901+p(r,l/2)%9901)%9901;}
}
int main()
{__int64 a,b,t,num=1;int i,j;scanf("%I64d%I64d",&a,&b);memset(ge,0,sizeof(ge));j=0;for(i=2;i*i<=a;++i)//得到次幂个数和质因数{if(a%i==0){ci[j]=i;while(a%i==0){a/=i;ge[j]++;}j++;}}if(a>1){ci[j]=a;ge[j++]=1;}for(i=0;i<j;++i){t=g(ci[i],ge[i]*b);num=(num*t)%9901;}cout<<num<<endl;return 0;
}POJ 2262 Goldbach's Conjecture
简单题，这题要说的不多，主要是素数判断这一块，算术基本定理，也称为素数的唯一分解定理，由此定理可以得出素数判断的循环次数。还有注意写的时候我的（int d=sqrt(x)）是判CE，所以要注意细节，因为编译器可能不会判断出来。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
bool check(int x)
{int i,d=int(sqrt(double(x)));//注意细节for(i=2;i<=d;++i){if(x%i==0){return false;}}return true;
}
int main()
{int n,i,f;while(cin>>n){f=0;if(n==0){break;}for(i=3;i<=n/2;++i)//注意范围{if(check(i)==true&&check(n-i)==true&&i%2==1&&(n-i)%2==1)//判断是否符合条件{printf("%d = %d + %d\n",n,i,n-i);f=1;break;}}if(f==0){cout<<"Goldbach's conjecture is wrong."<<endl;}}return 0;
}这篇关于唯一分解定理小练的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
