首页 > 代码库 > POJ 1845
POJ 1845
接下来交给大家一个网上查不到的解题方法
题目是酱找出a^b的因子的和答案对9901取模
我们将a可变成这样e1^x1*e2^x2...（ei为素数）
答案就变成这样(e1^0+e1^1...e1^x1)*(e2^0+e2^1...e2^x2)...
利用同余模定理我们可以知道每个e都能变成e%9901
而又由某元素作单位元生成的新的子群是循环的，并且在9901是素数的情况下我门可以知道x>= 2的时候生成的模9901后的数字是每9900个一循环并且不重复，那么当x>=2的时候我们就可以将幂模9900，0和1特判一下，简单观察就能知道0的时候return 1,1的时候return 幂+1；
over~
#include<stdio.h>#include<string.h>#include<iostream>using namespace std;//#define __int64 long longconst __int64 mod = 9901;__int64 ss(__int64 a, __int64 b){ a %= mod; if(a == 0)return 1; //if(a == 1) return b+1; b = b % (mod-1); __int64 ans = 0; __int64 m = 1; for(__int64 i =0 ;i <= b; i++){ ans += m % mod; ans %= mod; m = (m*a)%mod; } return ans;}int main(){ //freopen("in.cpp", "r", stdin); //freopen("out1.cpp", "w", stdout); __int64 a, b; while(cin>>a>>b){ if(a == 0 ){printf("0\n");continue;} __int64 ans = 1; for(__int64 i = 2; i*i <= a; i++){ __int64 k = 0; while(a%i == 0){ a/= i; k ++; } ans = (ans * ss(i, k*b))%mod; } if(a > 1) ans = (ans * ss(a,b))%mod; cout<<ans<<endl; }}
POJ 1845
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。