ckffl2010   1년 전

모든 예시를 다돌려봤는데 통과됐고 자꾸 1퍼에서 틀리네요 

일반적인 공식말고 공식자체를 역원계산말고 다른방법으로 풀어본건데 반례 부탁드립니다 형님들

#include

#include

using namespace std;

int mod=0;

long long CalPow_1(long long r, int exp1) // r^exp1을 계산하는 O(lgn)알고리즘

{

if(r==0)

return 0;

if(exp1==0)

return 1;

long long value=0;

value=CalPow_1(r,exp1/2);

if(exp1%2==0)

{

return (value*value);

}

else

{

return value*value*r;

}

}

long long CalPow(long long r, int exp1) // r^exp1을 계산하는 O(lgn)알고리즘

{

if(r==0)

return 0;

if(exp1==0)

return 1;

long long value=0;

value=CalPow(r,exp1/2);

if(exp1%2==0)

{

return (value*value)%mod;

}

else

{

return (((value*value)%mod)*(r%mod))%mod;

}

}

long long GetSum(int r, int n,int exp1)

{

if(n==2) //항의 수가 2개이면 1+r^(exp1) 반환

return (1+CalPow(r,CalPow_1(2,exp1)))%mod;

if(n%2==0) //항의 수 가 짝수면

{

return (((1+CalPow(r,CalPow_1(2,exp1)))%mod) * (GetSum(r,n/2,exp1+1)%mod)) %mod;

}

else // 항의 수 가 홀수면

{

return ((CalPow(CalPow(r,exp1+1),n-1)%mod)+GetSum(r,n-1,exp1))%mod;

}

}

int main()

{

int a,r,n;

cin>>a>>r>>n>>mod;

r%=mod;

if(n==1) cout<<(a%mod); //예외처리

else

{

cout<<(((long long)a%mod)*GetSum(r,n,0))%mod;

}

return 0;

}

댓글을 작성하려면 로그인해야 합니다.