Codeforces #176 Div2 D "Shifting"
ACしてるソースコードをカンニング
こうやって素直に変換するんじゃなくて
こうすればええんちゃうんか!
こうすれば青線のとこだけ数値を変更すればよく、
f( p, k )における計算量は、pの長さをnとすると、
n / kとなる。
全体の計算量は?
nを最大の100万として
k = 2 の時は50万回
k = 3 の時は33万回
k = 4 の時は25万回
k = 5 の時は20万回
...
int main(){ int n = 1000000; int cnt = 0; for( int k = 2; k <= n; k++ ){ cnt += n / k + (n % k ? 1 : 0); } cout << cnt << endl; }
( ^ V ^ )
ソースコード
int a[ 2000100 ]; int main(){ int n; scanf( "%d", &n ); // 初期の順列を作成 for( int i = 1; i <= n; i++ ){ a[i] = i; } // f(p, k) kを2~nまで試す for( int k = 2, shift = 1; k <= n; k++, shift++ ){ // 割り切れない場合 if( n % k ){ a[n + shift] = a[n + shift - n % k]; } // 後ろに下がるものだけ順次動かす for( int i = n / k; i >= 1; i-- ){ a[k * i + shift] = a[k * (i - 1) + shift]; } } // 出力 for( int i = n; i < n + n; i++ ){ printf( "%d ", a[i] ); } }