これも英語がわかりやすい問題。
降順と昇順で行くのかと一瞬思ったけど、サンプルからして違うっぽい。
10辺りまで解を見る為に、permutation全て試そうと思って、こんなん書く。
n = geti arr = (1..n).to_a min = [Infinity] max = [0] arr.permutation.each do |k| c = 0 tmp = 0 pd = 1 for i in k if c%i != 0 || c.zero? pd = pd.lcm(i) c += pd - c tmp += 1 end end min = [[tmp,k.dup],min].min max = [[tmp,k.dup],max].max end p [min,max] max[0] - min[0]
作りながら、lcm使ってるって事は素数のn乗とかを全部やりゃいいんじゃないかとか考えて、適当に書いたらサンプル通った。
ex)N=10
min:9,8,7,5,その他(LCM(9,8,7,5)は10以下の全てで割り切れる)
max:1,2,4,8,3,9,5,7,その他
よってminは素数の個数、maxは素数のn乗の個数的な。
def primeN(n) flg = [] primePowerList = [] resA = [0,1] cnt = 0 for i in 2..n if flg[i].nil? flg[i] = true cnt += 1 ii = i * i while ii <= n flg[ii] = false ii += i end ii = i while ii <= n primePowerList.push ii ii *= i end end resA[i] = cnt end primePowerList.sort! resB = [0,1] tmp = 1 for i in 2..n if primePowerList[tmp] == i tmp += 1 end resB[i] = tmp+1 end [resA,resB] end $pn,$ppn = primeN(10000) gcj_loop do n = geti $ppn[n] - $pn[n] end
投げてsmallAC.
明らかにLargeはオーダー的に通らないので、適当に書きすぎたのを修正しつつ、速度的に不安なのでC++に移行。
bool primef[1000020]; vector<int> plist; void initialize(){ ll max = 1000010; rep(i,max)primef[i]=true; primef[0]=primef[1]=false; int hoge = sqrt(max); for(ll i = 2; i <= hoge; ++i){ //ここ。ここさえ・・・ if(primef[i]){ plist.pb(i); ll ii = i * i; while(ii <= max){ primef[ii] = false; ii += i; } } } } ll n; ll Ipow(ll a,ll e){ ll res = 1; while(e){ if(e&1)res *= a; a *= a; e >>= 1; } return res; } void gcj_main(ostream &out){ cin>>n; ll sq = sqrt(n); ll res = 0; foreach(p,plist){ if(*p > sq)break; ll a = (ll)(log(n) / log(*p)); if(Ipow(*p,a+1)==n)a+=1; //cout<<*p<<" :"<<a<<endl; res += a - 1; } if(n == 1) out<<0<<endl; else out<<res+1<<endl; }
なんか出力小さいなぁと思いつつ投げる。コンテスト終了後WA。
素数リスト求めるのになんでsqrt(max)までしかやってないのかと100万回問い詰めたい。
素数フラグならいいけど、リスト作ってんだろうが・・・
//の所のhogeをmaxにしたら通った。
多分素数^n(n>=2)のリスト作ってソートして二分探索すれば速くなるけど、max入力で大丈夫だったのでそのまんま。
もしLarge通せていても時間的に500位は無理だったので、まぁ。
しかし、こういうミスは無くしたいなぁ・・・