CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes) D.K -good

前言

传送门 :

题解参考pzr :

思路

将题意转换为 n − k ∗ ( k + 1 ) 2 ≡ 0   m o d   k n-\frac{k*(k+1)}{2} \equiv 0\ mod \ k n−2k∗(k+1)​≡0 mod k

意为 n − k ∗ ( k + 1 ) 2 是 k 的 倍 数 n-\frac{k*(k+1)}{2} 是 k的倍数 n−2k∗(k+1)​是k的倍数 即 n − k ∗ ( k + 1 ) 2 = m ∗ k n-\frac{k*(k+1)}{2} =m*k n−2k∗(k+1)​=m∗k

n = m ∗ k + k ∗ ( k + 1 ) 2 n =m*k +\frac{k*(k+1)}{2} n=m∗k+2k∗(k+1)​ 即 n = k ∗ ( m + ( k + 1 ) 2 ) n=k*(m+\frac{(k+1)}{2}) n=k∗(m+2(k+1)​)

显然可以看出 , k 是 n 的 因 子 k是n的因子 k是n的因子

这里我们分类讨论一下

• 如果 k k k是偶数,那么 k 2 \frac{k}{2} 2k​也应该是 n n n的因子
• 如果 k k k是奇数,那么只能得出 k k k是 n n n的因子

我们将 n n n分解为 2 t ∗ s ( s 是 奇 数 ) 2^t*s(s是奇数) 2t∗s(s是奇数)

• 取 s s s,因为 s s s为奇数,所以由上面的性质可得 k = s k=s k=s
• 取 2 t 2^t 2t,因为 2 t 2^t 2t为偶数,所以由上面的性质可得 k 2 = 2 t \frac{k}{2}=2^t 2k​=2t

同时我们还需要使得 n − k ∗ ( k + 1 ) 2 > = 0 n-\frac{k*(k+1)}{2} >=0 n−2k∗(k+1)​>=0 因为如果考虑

从 1 + 2 + 3.. + k 1+2+3..+k 1+2+3..+k如果我们随便找一个数加上 k k k也是满足条件的

所以 n − k ∗ ( k + 1 ) 2 > 0 ∣ ∣ n − k ∗ ( k + 1 ) 2 = 0 n-\frac{k*(k+1)}{2} >0||n-\frac{k*(k+1)}{2} =0 n−2k∗(k+1)​>0∣∣n−2k∗(k+1)​=0

同时 k = s = 1 k=s=1 k=s=1是无解的,显然 s = 1 s=1 s=1的时候, k = 2 t + 1 k=2^{t+1} k=2t+1,所以

n − k ∗ ( k + 1 ) 2 = 2 t − k ∗ ( k + 1 ) 2 = 2 t + 1 − k ∗ ( k + 1 ) n-\frac{k*(k+1)}{2}=2^{t} -\frac{k*(k+1)}{2}=2^{t+1} -k*(k+1) n−2k∗(k+1)​=2t−2k∗(k+1)​=2t+1−k∗(k+1)

= 2 t + 1 − 2 t + 1 ∗ ( 2 t + 1 + 1 ) = 2 t + 1 ∗ ( 1 − ( 2 t + 1 + 1 ) ) < 0 显 然 =2^{t+1} -2^{t+1}*(2^{t+1}+1)=2^{t+1}*(1-(2^{t+1}+1)) < 0{显然} =2t+1−2t+1∗(2t+1+1)=2t+1∗(1−(2t+1+1))>n; ll s = n , q = 1; while(s%2 == 0 ){ s/=2; q*=2; } /** 将 n 拆分成 $s* (2^t)$ **/ if(q