c_Comp-Prog yukicoder No.2007 Arbitrary Mod (Easy)
解説と違ったのでリハビリがてら
問題
題意の通りです
解説
$ a \le 1000であること、$ 10^7 \le Mであることを踏まえると、
64bit整数型を持つことで$ a^n \lt 10^7となる場合とならない場合で場合分けができる。
$ a^n \lt 10^7の場合
$ a \ge 2であることから、$ a^n \ge 10^7となる最小の$ nは高々$ 30以下であることがわかる。
よってこの場合は愚直にかけることで判定できる。
$ a^n \ge 10^7の場合
この場合は愚直に掛けた後に$ a^x \le 10^7 (x \le n)となった際、その値$ a^xを$ Mとすることで
$ a^n(\mathrm{mod}\ M) \equiv a^x \times a^{(n-x)}(\mathrm{mod}\ M) \equiv 0(\mathrm{mod}\ M)
が満たされるため、
M
0
を出力すれば良い。
計算量は$ a^n \ge 10^7のときに使われる$ nが定数に変わることを考えると、
$ O(f(a,n))
ただし、
$ f(a,n) = \begin{cases} n & ( a^x \lt 10^7 ) \\ 1 & ( a^x \ge 10^7 ) \end{cases}
となる。
code:solve.cpp
using namespace std;
int main(){
long long a,n;cin>>a>>n;
long long nw = 1;
while(n && nw<10000000){
nw *= a;
n--;
}
if(nw<10000000){
cout << 10000000 << endl;
cout << nw << endl;
}else{
cout << nw << endl;
cout << 0 << endl;
}
}
感想
計算量があってるか自信がないです