15712번 - 등비수열
모든 예시를 다돌려봤는데 통과됐고 자꾸 1퍼에서 틀리네요
일반적인 공식말고 공식자체를 역원계산말고 다른방법으로 풀어본건데 반례 부탁드립니다 형님들
#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)알고리즘
value=CalPow(r,exp1/2);
return (value*value)%mod;
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); //예외처리
cout<<(((long long)a%mod)*GetSum(r,n,0))%mod;
댓글을 작성하려면 로그인해야 합니다.
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;
}