BRUTEFORCE 문제에 관해 질문들입니다. shinhj88 등비수열의 합을 구하는 공식을 이용하여 구하였습니다. r^n (r^m+1-n-1)/(r-1) 그런데 마지막 3567404 46749457 21 이데이터에서 오류가 나옵니다 제생각엔 나머지 구하는 부분에서 오차가 나는것같은데 도저히 오차를 수줄이지 못해 질문을 드립니다. 해결해주세요~~ ㅠㅠ #include <iostream> #include <cstdlib> using namespace std; const unsigned long long int MOD= 1000000007; long n,m; long long int c; bool flag=true; unsigned long long int BRUTEFORCE(long N) { if(N==1)return c; if(N%2==0) { unsigned long long int a=BRUTEFORCE(N/2); return (a*a+MOD)%MOD; } else { unsigned long long int a=BRUTEFORCE(N-1); return (a*c+MOD)%MOD; } } int main() { int T; unsigned long long int ans; scanf("%d",&T); while(T--) { flag=true; cin>>n>>m>>c; unsigned long long int b,a; if(c==1) { a=m; b=n-1; cout<<a-b; } else { a=(BRUTEFORCE(m+1-n)-1)/(c-1); b=BRUTEFORCE(n); ans=(a*b)%MOD; cout<<ans<<endl; } } } 11년 전
2개의 댓글이 있습니다. Being 아쉽게도 (a % X) / b와 (a / b) % X는 다릅니다. 예를 들어 a = b = X = 2 라고 하면, 앞의 식은 0이 나오고 뒤의 식은 1이 나오겠지요. 이 문제에서 위와 같은 방식으로 계산하기는 어려울 것 같습니다. 11년 전 link Being 꼭 나눗셈을 하고 싶으시다면 1000000007 이 소수이므로 이 특성을 활용하는 방법이 한 가지 있기는 합니다만, 그 방법을 사용하지 않으셔도 해결할 수 있을 것 같습니다. 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
shinhj88
등비수열의 합을 구하는 공식을 이용하여 구하였습니다.
r^n (r^m+1-n-1)/(r-1)
그런데
마지막 3567404 46749457 21
이데이터에서 오류가 나옵니다
제생각엔 나머지 구하는 부분에서 오차가 나는것같은데
도저히 오차를 수줄이지 못해 질문을 드립니다.
해결해주세요~~ ㅠㅠ
11년 전