This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <functional>
#include <list>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <map>
#define MOD 1000000007
using namespace std;
long long dnq(long long a, int n)
{
if (n == 1)
return a%MOD;
if (n % 2 == 0)
{
long long k = dnq(a, n / 2);
return (k*k)%MOD;
}
else
return (a*dnq(a, n - 1))%MOD;
}
int main() {
//freopen("input.txt", "r", stdin);
long long n;
scanf("%lld", &n);
vector<pair<int, int> > v;
v.push_back(make_pair(1, 1));
v.push_back(make_pair(2, 2));
long long ans = 4;
if (n == 1)
ans = 1;
else if (n == 2)
ans = 2;
else if (n == 3)
ans = 4;
else {
for (long long g = 3, k = 3, t = 1, j = 1; k < n; g++)
{
v.push_back(make_pair(g, v[t].first));
if (k + v[t].first > n)
ans = (ans * dnq(g, n - k)) % MOD;
else
ans = (ans * dnq(g, v[t].first)) % MOD;
k += v[t].first;
j++;
if (j >= v[t].second)
{
t++;
j = 0;
}
}
}
printf("%lld\n", ans);
}
Compilation message (stderr)
FG.cpp: In function 'int main()':
FG.cpp:36:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &n);
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |