「CF1246X」Codeforces Round #596 (Div. 1)

2019年12月3日690

A. p-binary
最终答案不超过 logn,枚举答案 i,找出 n – i * p 在二进制下 1 的个数

B. Power Products

想了一个比较复杂的做法

先把所有在 10^10 以内的,能表示成 x^k 的数存起来

若 k = 2,对于每个数 ai,把 ai 的平方因子除掉以后得到 y,和它配对的数一定是 y * t^2

若 k > 2,10 ^ 10 内 x^k 数至多 2 万个,枚举一个数,暴力找另一个和它配对的数

比较简单的做法是,先把每个数做质因数分解,把指数取模 k 以后,找与它互补的数的倍数计数即可

avatar
  Subscribe  
提醒