太阳神 [莫比乌斯反演]

太阳神 [莫比乌斯反演]

比较容易想到，先将 > n 转换成 <= n

然后就可以直接暴力枚举 l，然后快速计算 (d, i, j) 的对数

#include#define N 100050using namespace std;typedef long long ll;const int Mod = 1000000007;ll n;int prim[N], isp[N], mu[N], tot;void prework(){ mu[1] = 1; for(int i = 2; i <= N-50; i++){ if(!isp[i]) prim[++tot] = i, mu[i] = -1; for(int j = 1; j <= tot; j++){ if(i * prim[j] > N-50) break; isp[i * prim[j]] = 1; if(i % prim[j] == 0){ mu[i * prim[j]] = 0; break;} mu[i * prim[j]] = mu[i] * mu[prim[j]]; } }}int main(){ scanf("%lld", &n); prework(); ll x = n % Mod, ans = (x * x) % Mod; for(ll i = 1; i * i <= n; i++){ if(!mu[i]) continue; ll m = n / i / i, sum = 0; for(ll a = 1; a * a * a <= m; a++){ for(ll b = a; a * b * b <= m; b++){ ll c = m / a / b - b + 1; if(a == b) sum = (sum + 1 + (c - 1) * 3) % Mod; else sum = (sum + 3 + (c - 1) * 6) % Mod; } } ans = (ans - mu[i] * sum) % Mod; } cout << (ans % Mod + Mod) % Mod; return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。