SRM596 DIV2 1000

数论题，注意以下性质：

(1) 若 ( divisor | F(n) ) 则必存在整数 (r) 使得 ( n equiv r^2 (mod divisor) (r in mathbf{N}且n>r^2) )

(2) 若 ( n equiv r^2 (mod divisor) (r in mathbf{N}且n>r^2) ) 则必有 ( divisor | F(n) )

若 (divisor) 不是质数则性质不成立，因此原题转换为如下问题：

求区间 ( [lo, hi] ) 内满足 ( n equiv r^2 (mod divisor) (r in mathbf{N}且n>r^2) ) 的所有不同的n的个数

利用同余的性质来对n进行划分：

定义 ( S(r) ) 为所有 ( n(r) ) 的集合

(1) 若 ( r_1^2 ot equiv r_2^2 (mod divisor) ) 则 ( S(r_1) cap S(r_2) = emptyset )

(2) 若 ( r_1^2 equiv r_2^2 (mod divisor) ( r_1>r_2 ) ) 则 ( S(r_1) subseteq S(r_2) )

式(2)可以这样来看，(r) 越小 (n>r^2) 造成的n的下限就越小，所以 (S(r)) 的范围就越大

因此将所有的 (n(r)) 按照除以 (divisor) 的余数进行划分，对每一个划分，只保留最小的那个 (r) 的 (S(r)) 即 (S(r_{min}) )

若 (n leq max)则：

(S(r)={r^2+d, r^2+2d, r^2+3d, ..., r^2+kd | r^2+kd leq max 且 r^2+(k+1)d > max })

(|S(r)|=(max-r^2) // divisor )

( sum S(r_{min}) ) 即为所求，记得还要考虑 (n) 所在的区间 ([lo, hi])，

【优化】

更深层次的推导可以得出以下结论：

( sum_{r=0}^{divisor//2}S(r) ) 即为所求

猜测应该跟同余性质有关，但不知道怎么证，下面只给出没有优化过的代码

 1 class SparseFactorialDiv2:
 2     def getCount(self, lo, hi, divisor):
 3         return self.calc(hi, divisor) - self.calc(lo-1, divisor)
 4         
 5     def calc(self, ran, divisor):
 6         mods = [False] * divisor
 7         y = 0
 8         tot = 0
 9         while y * y < ran:
10             r = y * y % divisor
11             if not mods[r]:
12                 mods[r] = True
13                 tot += (ran - y*y) // divisor
14             y = y + 1
15         return tot
16     
17     
18     
19 
20 # test
21 o = SparseFactorialDiv2()
22 
23 # test: hi == lo
24 assert(o.getCount(1,1, 3) == 0)
25     
26 # test case
27 assert(o.getCount(4, 8, 3) == 3)
28 assert(o.getCount(9, 11, 7) == 1)
29 assert(o.getCount(1, 1000000000000, 2) == 999999999999)
30 assert(o.getCount(16, 26, 11) == 4)
31 assert(o.getCount(10000, 20000, 997) == 1211)
32 assert(o.getCount(123456789, 987654321, 71) == 438184668)
33 print('ok')

View Code