Official
C - Cream puff Editorial by kyopro_friends
要するに「\(N\)の約数を列挙してください」という問題です。
制約が大きいため、\(1\)~\(N\) まですべてを試していては間に合いません。計算量を減らす方法を考えましょう。
「\(d\) が \(N\) の約数である」ことと「\(N/d\) が \(N\) の約数である」ことは同値です。つまり、\(\sqrt{N}\) より大きな \(N\) の約数は、必ず \(\sqrt{N}\) より小さな \(N\) の約数と対になります。
例えば \(N=20\) のとき、\(20\) は\(1\) と、\(10\) は \(2\) と、\(5\) は \(4\) と対になります。
よって、\(\sqrt{N}\) までを全探索しながら、\(d\) と \(N/d\) を同時に約数として記録していくことで、\(O(\sqrt{N})\) の時間でこの問題を解くことができました。
実装によっては、\(N\) が平方数の場合に注意が必要です。
以下の解答例ではsetを使っているため計算量は約数の個数を \(k\) として \(O(\sqrt{N}+k\log k)\) になっています。
#include <bits/stdc++.h>
using namespace std;
int main(){
long n;
cin >> n;
set<long> ans;
for(long d=1;d*d<=n;d++){
if(n%d==0){
ans.insert(d);
ans.insert(n/d);
}
}
for(auto x:ans)cout << x << endl;
}
posted:
last update: