讨论/面试考题/中国移动的坑货编程题,这题神仙能做?/
中国移动的坑货编程题,这题神仙能做?

Snipaste_2020-05-13_20-23-36.png
Snipaste_2020-05-13_20-23-56.png

展开讨论
在路上发起于 2020-05-13

N的因子数量是奇数 -> N = a^2
对 a 质因数分解有 a = a1i1a2i2...anina_1^{i_1} * a_2^{i_2} *... * a_n^{i_n} , a1~an为互不相同的质数
则 N = a12i1a22i2...an2ina_1^{2i_1} * a_2^{2i_2} *... * a_n^{2i_n}
记N的因子数量为f(N)f(N)
f(N)f(N) = (2i1+1)(2i2+1)...(2in+1)(2i_1+1)*(2i_2+1)*...*(2i_n+1)
f(N)f(N) 为质数,则 n = 1 且 2i1i_1+1为质数
综上,若N的因子数量是奇数,则有 N=a2iN = a^{2i},其中aa为质数,2i+12i+1为质数
注意到a的上届是10^7,打个素数表遍历就行了

2
展开全部 5 讨论