반응형
https://algospot.com/judge/problem/read/BRUTEFORCE
algospot.com :: BRUTEFORCE
Brute-Force Attack 문제 정보 문제 암호학에서 Brute-Force Attack 은, 암호를 풀기 위해서 무식하게 수많은 암호를 하나하나 시도하는 방법을 일컫는다. 대부분의 경우 Brute-Force Attack 을 사용하는 것은 무
algospot.com
1. 단순 계산 → 비효율적임.
2. 등비수열의 합 → '1000000007'으로 나누는 부분에서 문제 발생.
3. 점화식(규칙) 찾기
3번으로 해결함. 단, 코드는 다른 포스팅의 도움을 받음.
#include
#include
#define R 1000000007LL
typedef long long long64;
long64 POW(long64 base, long64 limit)
{
if (limit == 1)
return base;
else if (limit == 0)
return 1;
else
{
long64 exp = 1, mod = base;
while (exp * 2 <= limit)
{
mod = (((mod % R)*(mod % R)) % R);
exp *= 2;
}
return (mod * POW(base, limit - exp)) % R;
}
}
long64 RN(long64 base, long64 exp)
{
if (exp <= 1)
return 1;
else
{
long64 mod1, mod2;
if (exp % 2 == 0)
{
mod1 = RN(base, exp / 2);
mod2 = (1 + POW(base, exp / 2)) % R;
return (mod1*mod2) % R;
}
else
{
mod1 = RN(base, exp - 1);
mod2 = POW(base, exp - 1);
return (mod1 + mod2) % R;
}
}
}
int main()
{
int T;
for (scanf("%d", &T); T > 0; T--)
{
int A, B, N;
scanf("%d %d %d", &A, &B, &N);
long64 mod1, mod2, Sn = 0;
if (N == 1)
Sn = B - A + 1;
else
{
int n = B - A + 1;
mod1 = POW(N, A);
mod2 = RN(N, n);
Sn = (mod1 * mod2) % R;
}
printf("%lu\n", Sn);
}
return 0;
}반응형