点击打开链接poj 1845
思路:数学+二分
分析:
1 题目要求的是A^B的所有因子的和对9901取模
2 先看几个数学定理
1:整数的唯一分解定理(如果A本身就是素数的话,那么本身就是分解式)
任意正整数都有且只有一种方式写出其素因子的乘积表达式。
A = (p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn) 其中pi均为素数;
A^B = p1^(k1*B) * p2^(k2*B)*...* pn^(kn*B);
2:约数和公式
对于已经分解的整数A = (p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)
则A的所有因子之和为
sum = (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)
则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:同余模公式
(a+b)%m=(a%m+b%m)%m
(a*b)%m=(a%m*b%m)%m
(a-b)%m=(a%m-b%m)%m
3 那么假设我们现在求出了A的分解式的pi和ki,那么现在要求的是约数的和,如果直接进行求解的话肯定是会溢出long long的,所以直接求这个思路是不行的。
我们现在来考虑这两个数组
1+p1+p2+p3+p4+p5+p6+p7 = (1+p1+p2+p3)+p4*(1+p1+p2+p3) = (1+p4)*(1+p1+p2+p3);
1+p1+p2+p3+p4+p5+p6 = (1+p1+p2)+p4*(1+p1+p2) + p3 = (1+p4)*(1+p1+p2) + p3;
那么推广到一般的n,就可以分成n是奇数和n是偶数的情况,然后利用上面的最右边的式子求ans。但是如果直接求是不行的,这个时候你可以仔细观察一下这个式子的一般式
如果n数奇数: (1+p^(n/2+1))*(1+p1+...+p^(n/2)); 如果n是偶数:(1+p^(n/2+1))*(1+p1+...+p^(n/2))+p^(n/2);
根据(1+p1+...+p^(n/2)),这个就是原式的一半,那么根据这个规律我们就可来利用递归每一次都进行二分求解即可。
4 注意取模的运用,像这一类的题目,数据量很大的都是要用long long。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long int64;
#define MAXN 100010
#define MOD 9901
int64 a , b , pos , ans;
int64 p[MAXN] , k[MAXN];
/*求出a的分解式的pi和ki*/
void prime(){
pos = 0;
for(int64 i = 2 ; i*i <= a ; i++){
if(a%i == 0){
p[pos] = i;
k[pos] = 0;
while(a%i == 0){
k[pos]++;
a /= i;
}
pos++;
}
}
/*假设a本身就是一个素数*/
if(a != 1){
p[pos] = a;
k[pos++] = 1;
}
}
/*快速幂求次方*/
int64 Pow(int64 x , int64 y){
int64 tmp = 1;
while(y){
if(y&1)
tmp = (tmp%MOD)*(x%MOD)%MOD;
y >>= 1;
x = (x%MOD)*(x%MOD)%MOD;
}
return tmp;
}
/*二分求解等比数列的和1+x+x^2+x^3...+x^y*/
int64 sum(int64 x , int64 y){
if(y == 0)
return 1;
/*是奇数*/
if(y&1)
return (sum(x , y/2)%MOD)*((1+Pow(x , y/2+1))%MOD)%MOD;
/*是偶数*/
else
return ((((sum(x , y/2-1)%MOD)*((1+Pow(x , y/2+1))%MOD))%MOD) + (Pow(x , y/2)%MOD))%MOD;
}
int main(){
while(scanf("%lld%lld" , &a , &b) != EOF){
prime();
/*求和*/
ans = 1;
for(int i = 0 ; i < pos ; i++)
ans = (ans%MOD)*(sum(p[i] , k[i]*b)%MOD)%MOD;
printf("%lld\n" , ans);
}
return 0;
}
分享到:
相关推荐
北大POJ1845-Sumdiv 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj分类poj分类poj分类poj分类
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1083的代码,POJ1083的代码,POJ1083的代码
Poj中一些题目的源代码,里面共有二十多道题目,OI
poj 百练 题目分类 poj 百练 题目分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码