心得（一）
存在函数 _is(x) 表示 x 是否满足某种性质 ，满足性质函数=1，反之=0
存在函数 ：
求：
一下提供两个思路求解
题目参考链接https://codeforces.com/contest/2091/problem/E
题目描述：存在多少对a，b st. 1<=a<b<=n 并且 lcm(a,b)/gcd(a,b)为素数
思路：lcm(a,b)/gcd(a,b)=(a/gcd(a,b))*(b/gcd(a,b))为素数 排除两种可能后得 a=gcd(a,b) 且 b%a==0 且 isprime(b/a)==1
即对于1<=i<j<=n 枚举每个i 找到所有x st.i*x<=n 且 isprime(x) 即 求sumprime(n/i)
问题转化为求
每种思路都要先用筛 预处理出1e7以内所有素数（或者打表）
思路一：
在O(根号n)时间复杂度内可以解决问题
但是对于最上面的问题，不能每次都找到一个展开式将On时间复杂度降到O根号n时间复杂度
于是有了思路二：
这里只需遍历每个素数，对于每个素数，他在n/i上都有贡献，累加贡献就好
打表的话时间复杂度为O(Π(n))=O(n/logn) 似乎没有O(根号n)时间复杂度要好，但是对于大多数求解最上面问题的时候，只能去寻找_is(i)对于问题f(i)的贡献
https://ac.nowcoder.com/acm/contest/104420/A
这里以这道题为例
题目描述 ：存在多少对a，b st. 1<=a<b<=n 并且 a+b=x^2 并且 x为正整数
即 对于每个i st.i<j<=n && j=x^2-i 等价于 对于每个i 2*i<x^2<=n+i 找到 (2*i,n+i] 范围内所有x^2
即求：
sumpowx(i)表示 i 以内包含多少个x^2
也就是求解最上面那个公式
若直接求解考虑二分，时间复杂度依旧有Onlogn 递推也无法降低时间复杂度
那么只能通过思路二 枚举每个x^2求解
对于求解
枚举x^2 找到他在n+i上的贡献，若x^2<=n+1 对于n+1到n+n-1每个都有贡献 res+=n-1 ，若x^2>n+1 则找到x^2=n+j
j=x^2-n 大于等于 j 的所有i有 2*n-x^2 个，res+=2*n-x^2 1<=x^2<=n+n-1
同理后面sumpowx求和依旧通过找贡献求得
枚举x^2只需枚举根号n个 时间复杂度降到O根号n
总结：对于求 _sum(f(i)) 求和的问题，可以通过找到 _is(i) 在 f(i) 上的贡献求和，如果数学功底好可以尝试递推出其他式子