POJ 1845 Sumdiv
11846 단어 div
Time Limit: 1000MS
Memory Limit: 30000K
Total Submissions: 10515
Accepted: 2477
Description
Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).
Input
The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.
Output
The only line of the output will contain S modulo 9901.
Sample Input
2 3
Sample Output
15
Hint
2^3 = 8.
The natural divisors of 8 are: 1,2,4,8. Their sum is 15.
15 modulo 9901 is 15 (that should be output).
Source
Romania OI 2002
A^B mod 9901
A p1^a1*p2^a2*..*pk^ak
gcd(pi-1,9901)!=1
、、、、
1+p1+p1^2...p^n
n%2==1
=(1+p+p^2+..p^(n/2))(1+p^(n/2+1))
n%2==0
n=n-1;
=(1+p+p^2+..p^(n/2))(1+p^(n/2+1))+p^(n+1);
a 9901 , tp ,Wa 、、、
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
int x,y;
#define Mod 9901
void EGcd(int a,int b)
{
if(b==0)
{
x=1;
y=0;
return ;
}
EGcd(b,a%b);
int x0=y;
y=x-a/b*y;
x=x0;
}
int gcd(int a,int b)
{
int r;
while(r=a%b){a=b;b=r;}
return b;
}
#define N 10002
bool h[N];
int pm[N>>1];
void Getprime()
{
int cnt=1;
int i,j;
pm[0]=2;
for(i=2;i<N;i+=2)
h[i]=1;
for(i=3;i<N;i+=2)
if(!h[i])
{
pm[cnt++]=i;
for(j=i*i;j<N;j+=i)
h[j]=1;
}
}
int Pw(int a,int b)
{
int t;
for(t=1;b>0;b=(b>>1),a=(a%Mod)*(a%Mod)%Mod)
if(b&1) t=(t*a)%Mod;
return t;
}
int bn(int a,int n)
{
if(n==2)
{
return (1+a+(a%Mod)*(a%Mod)%Mod)%Mod;
}
if(n==1)
{
return (1+a)%Mod;
}
if(n%2)
{
return bn(a,n/2)*(1+Pw(a,n/2+1)%Mod)%Mod;
}
n--;
return bn(a,n/2)*(1+Pw(a,n/2+1)%Mod)%Mod+Pw(a,n+1);
}
int rc[12][2];
int main()
{
Getprime();
int a,b;
int tp;
while(scanf("%d %d",&a,&b)!=EOF)
{
if(a==0){printf("0
");continue;}
if(b==0||a==1){printf("1
");continue;}
tp=1;
int m=(int)sqrt(a*1.0);
int i,cnt=0;
for(i=0;pm[i]<=m;i++)
if(a%pm[i]==0)
{
rc[cnt][0]=pm[i];
rc[cnt][1]=0;
while(a%pm[i]==0){a/=pm[i];rc[cnt][1]++;}
cnt++;
}
if(a>1) { rc[cnt][0]=a;rc[cnt++][1]=1;}
for(i=0;i<cnt;i++)
{
if(gcd(rc[i][0]-1,Mod)==1)
{
tp=tp*(Pw(rc[i][0],rc[i][1]*b+1)-1)%Mod;
while(tp<0)tp+=9901;// 、、、Wa
EGcd(rc[i][0]-1,9901);
while(x<0)x+=9901;
tp=tp*(x%9901)%9901;
}
else
{
tp=tp*bn(rc[i][0],rc[i][1]*b)%9901;
}
}
printf("%d
",tp);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
🧙🏼 HTML 구조를 나타내는 요소: 컨텐츠 분할 요소 : 블록 레벨 요소 : 플로우 콘텐츠를 위한 통용 컨테이너 (순수 컨테이너로서 아무것도 표현안함) : 인라인 컨테이너 : 인라인 레벨 요소 🌵 span (인라인 요소) vs div(블록 요소) ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.