codeforces：E1.LCMSum(easyversion)【数论问题+不合法的情况求出来】

分析

根据最大的k
分类谈论lcm的值
只有当lcm &＃61; k
或lcm &＃61; 2k 且 i &＃43; j > k才是bad的
一个是求每个数的因数个数&＃xff0c;然后匹配两个
另一个就是妥妥的数论求解
详解解法见注释

Ac code

import sys
import mathinput &＃61; sys.stdin.readlinefor _ in range(int(input())):l, r &＃61; list(map(int, input().split()))tot &＃61; math.comb(r - l &＃43; 1, 3)# i # [i, j, k] >&＃61; 3k, good# [i, j, k] &＃61;&＃61; k, bad# [i, j, k] &＃61;&＃61; 2k and i &＃43; j > k, bad# we want to calculate the total bad# tot good &＃61; tot - tot bad# [i, j, k] &＃61;&＃61; k, bad &＃61;> easy# k % i &＃61;&＃61; 0 and k % j &＃61;&＃61; 0# valid_factor[i] means i has how many factor in [l, r &＃43; 1], not including i itselfvalid_factor &＃61; [0] * (r &＃43; 1)for x in range(l, r &＃43; 1):mul &＃61; 2while mul * x <&＃61; r:valid_factor[mul * x] &＃43;&＃61; 1mul &＃43;&＃61; 1for i in range(l, r &＃43; 1):tot -&＃61; valid_factor[i] * (valid_factor[i] - 1) // 2# [i, j, k] &＃61;&＃61; 2k and i &＃43; j > k and i # we want to find out the relation between i, j, k# amazing# i &＃43; j > k &＃61;> j > k / 2# let m satisfied: j * m &＃61; 2k &＃61;> j &＃61; (2 / m) k > (1 / 2) k# m <4; and it&＃39;s easy to see m > 2; therefore m &＃61; 3# Thus, j &＃61; (2 / 3) k# cause i &＃43; j > k and i # (1 / 3) k # again, let n satisfied: i * n &＃61; 2k &＃61;> i &＃61; (2 / n) k# therefore: (1 / 3) k <(2 / n) k <(2 / 3) k# easy to see: n &＃61; 4 or n &＃61; 5# therefore, i &＃61; (2 / 4) k or i &＃61; (2 / 5) k# change into integer, two solutions:# i : j : k &＃61; 3 : 4 : 6# i : j : k &＃61; 6 : 10 : 15for k in range(l, r &＃43; 1):# i : j : k &＃61; 3 : 4 : 6if k % 6 &＃61;&＃61; 0 and (2 * k) // 3 >&＃61; l and k // 2 >&＃61; l:tot -&＃61; 1# i : j : k &＃61; 6 : 10 : 15if k % 15 &＃61;&＃61; 0 and (2 * k) // 3 >&＃61; l and (2 * k) // 5 >&＃61; l:tot -&＃61; 1print(tot)


总结