Codeforces Beta Round #85 Div. 1 Only

Codeforces Beta Round #85 Div. 1 Only (9/4 21:00~23:00）

■A. Petya and Inequiations

問題

n,x,yが与えられる．
a₁²+a₂²+…+a_n²≥x
a₁+a₂+…+a_n≤y
を満たす正整数の列
a₁,a₂,…,a_n
を求めよ．なければ，-1を返せ．

解法

a₁+a₂+…+a_n
の最小値はn．次に，
a₁+a₂+…+a_n=y
としたとき，
a₁²+a₂²+…+a_n²
の最大値は，
a_k=1 (1≤k≤n-1)
a_n=y-(n-1)
のとき，この値（=(n-1)+(y-(n-1))²）がx以上なら数列(a^k)が答え．
#85 Div. 1 A. Petya and Inequiations

■B. Petya and Divisors

問題

2つの数列
x₁,…,x_n
y₁,…,y_n
が与えられる．
各(x_i, y_i)について，
x_i mod k=0 かつ (∀j:i-y_i≤j<i) x_j mod k ≠ 0
なる正整数kの数を求めよ．

解法

x_iの各約数d_i,kについて，
それがx₁,…,x_i-1の約数である最後のインデックスp[d_i,k]を記録しておく．
p[d_i,k]<i-y_iなら条件を満たす．
その後，
p[d_i,k]=i
と更新．
#85 Div. 1 B. Petya and Divisors

■Result

o---- 484pts. 278th
1689 -> 1684

ドカーン．