求a_i 在 [1,k]范围内,gcd(a_1,a_2...,a_n) = 1的a的数组个数。
F(x)表示gcd(a_1,a_2,...,a_n) = i的a的个数
f(x)表示gcd(a_1,a_2,...,a_n) = ki的a的个数(实际上就是i的倍数)
f(x) = segma(x | d) F(d)
F(x) = segma(x | d) mu(d / x) * f(d)
F(1) = segma(d,1,k) mu(d) * f(d)
f(d) = (k / d)^n
由于k变化时f数组会发生变化但为了要避免不断更新f数组，我们把和式换一种方式去求。
由于k增大后，只有k的因子t对应的f数组f(t)加1，因此大可以用筛法枚举因子i，找到该因子的对应倍数j
然后更新答案，其中每次变化贡献的值应为mu(i) * (f(j / i) - f(j / i - 1))，然后更新ans，加上已经枚举完的因子i对应的答案。
#include <cmath> #include <cstdio> #include <cstdlib> #include <cassert> #include <cstring> #include <set> #include <map> #include <list> #include <queue> #include <string> #include <iostream> #include <algorithm> #include <functional> #include <stack> using namespace std; typedef long long ll; #define T int t_;Read(t_);while(t_--) #define dight(chr) (chr>='0'&&chr<='9') #define alpha(chr) (chr>='a'&&chr<='z') #define INF (0x3f3f3f3f) #define maxn (2000005) #define maxm (10005) #define mod 1000000007 #define ull unsigned long long #define repne(x,y,i) for(int i=(x);i<(y);++i) #define repe(x,y,i) for(int i=(x);i<=(y);++i) #define repde(x,y,i) for(int i=(x);i>=(y);--i) #define repdne(x,y,i) for(int i=(x);i>(y);--i) #define ri register int inline void Read(int &n){char chr=getchar(),sign=1;for(;!dight(chr);chr=getchar())if(chr=='-')sign=-1; for(n=0;dight(chr);chr=getchar())n=n*10+chr-'0';n*=sign;} inline void Read(ll &n){char chr=getchar(),sign=1;for(;!dight(chr);chr=getchar())if (chr=='-')sign=-1; for(n=0;dight(chr);chr=getchar())n=n*10+chr-'0';n*=sign;} /* */ int mu[maxn],isprim[maxn],prim[maxn],len,n,k; ll sum[maxn],p[maxn]; void mui(){ mu[1] = 1; repe(2,k,i){ if(!isprim[i]) mu[prim[len++] = i] = -1; repne(0,len,j){ if(i * prim[j] > 2000000) break; isprim[i*prim[j]] = true; if(i % prim[j] == 0) break; mu[i*prim[j]] = -mu[i]; } } } ll quickpow(ll x,ll y){ ll ans = 1; while(y){ if(y & 1) ans = (ans * x) % mod; x = (x * x) % mod; y >>= 1; } return ans; } void solve(){ p[0] = 0,p[1] = 1; repe(2,k,i) p[i] = quickpow(i,n); int s = 0,ans = 0; repe(1,k,i){ for(int j = i;j <= k;j += i) sum[j] = ((sum[j] + (ll)mu[i]*(p[j/i] - p[j/i-1])) + mod) % mod; s = (s + sum[i]) % mod; ans = (ans + (s^i)) % mod; } cout << ans << endl; } int main() { /// freopen("a.in","r",stdin); // freopen("b.out","w",stdout); Read(n),Read(k); mui(); solve(); return 0; }
---恢复内容结束---