长期更新
我已经差不多是个打表+优化暴力+卡常选手了
为了方便都用S(n)表示n*(n+1)/2
1026
为了方便以下用n代指a+n-1,用m代指b+m-1
总的情况减掉重复的数就是所有不同的数。
考虑一个数p满足$a<=p^{sta}<p^{end}<=n$，那么设[sta,end]={a_{1},a_{2},...a_{end-sta+1}
重复的情况就是对于满足一个$\sum_{l=b}^{m}lcm(a_{k1},a_{k2},a_{k3}...a{ks})|l*(-1)^{s+1}$
lcm增长起来非常快所以可以省掉很多冗余的枚举。O(跑得过),V3不会做
#include<cstdio>
using namespace std;
int a,b,n,m,cnt,num,last;
int sta[710],ed[710];
bool vis[1000005];
long long ans;
inline int gcd(int x,int y){return x==0?y:gcd(y%x,x);}
inline int lowbit(int k){return k&-k;}
int main(){
scanf("%d%d%d%d",&m,&n,&a,&b);
ans=1LL*m*n;
m=b+m-1;n=a+n-1;
for(int i=2;i<=n;i++)if(!vis[i]){
long long now=i;
cnt++;
ed[cnt]=1;sta[cnt]=0;
while(now<=n){
if((now>=a)&&(sta[cnt]==0))sta[cnt]=ed[cnt];
ed[cnt]++;
vis[now]=true;
now=now*i;
}
ed[cnt]--;
if((sta[cnt]>=ed[cnt])||(sta[cnt]==0))cnt--;
}
for(int i=1;i<=cnt;i++){
if((sta[i]==sta[i-1])&&(ed[i-1]==ed[i])){ans+=last;continue;}
last=0;
for(int j=3;j<(1<<(ed[i]-sta[i]+1));j++){
if(lowbit(j)==j)continue;
int p=1,Min=0,Max,s=0;
for(int k=sta[i];k<=ed[i];k++)if(j&(1<<(k-sta[i]))){
Max=k;
if(!Min)Min=k;
s++;
p=1LL*p*k/gcd(p,k);
}
Min=p/Min;
Max=p/Max;
if(m/Min-(b-1)/Max<=0)continue;
int tmp;
if(s&1)tmp=m/Min-(b-1)/Max;
else tmp=(b-1)/Max-m/Min;
ans+=tmp;
last+=tmp;
}
}
printf("%lld",ans);
}
1192
原题，但我上次忘记写了_(:зゝ∠)_BZOJ2820gcd=1也就这个套路了
$\sum_{prime(p)}\sum_{i=1}^{n/p}\sum_{j=1}^{m/p}e(gcd(i,j))$
$\sum_{prime(p)}\sum_{d=1}^{n/p}\mu(d)[n/pd]*[m/pd]$
$\sum_{i=1}^{n}[n/i]*[m/i]\sum_{p|i,prime(p)}\mu(i/p)$
$\sum_{p|i,prime(p)}\mu(i/p)$可以线性筛之后线性时间内搞出来，每次询问根号时间枚举n/i和m/i就可以了
#include<cstdio>
using namespace std;
int sum[5000005],f[5000005],last[5000005],prime[670000],s[5000005],mu[5000005],p[5000005];
int n,m,test,cnt;
void pre(int n){
mu[1]=1;
for(int i=2;i<=n;i++){
if(!last[i]){last[i]=1;prime[++cnt]=i;s[i]=1;mu[i]=-1;p[i]=i;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=n);j++){
int k=prime[j]*i;p[k]=prime[j];
if(i%prime[j]==0){last[k]=last[i];s[k]=s[i]+1;mu[k]=0;break;}
else{last[k]=i;s[k]=1;mu[k]=-mu[i];}
}
}
}
inline int read(){
int ret=0;
char c=getchar();
while((c>'9')||(c<'0'))c=getchar();
while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ret;
}
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
int main(){
pre(5000000);
for(int i=2;i<=5000000;i++){
if(s[i]==1)f[i]=-f[last[i]]+mu[last[i]];
else if(s[i]==2)f[i]=mu[i/p[i]];
else f[i]=0;
sum[i]=sum[i-1]+f[i];
}
test=read();
while(test--){
n=read();m=read();
if(n>m){int t=n;n=m;m=t;}
int kn=1,km=m/n,last=n;
long long ans=0;
while(true){
int x=min(last-1,max(n/(kn+1),m/(km+1)));
ans+=1LL*(sum[last]-sum[x])*kn*km;
if(x==0)break;
last=x;kn=n/x;km=m/x;
}
printf("%lld\n",ans);
}
}
1237
先套路
$\sum_{d=1}^{n}d\sum_{k=1}^{n/d}\mu(k)([n/dk])^{2}$
$\sum_{i=1}^{n}([n/i])^{2}\sum_{d|i}\mu(d)*i/d$
考虑$\sum_{d|i}\mu(d)*i/d$的前缀和之后就可以枚举n/i做
$\sum_{i=1}^{n}\sum_{d|i}\mu(d)*i/d=\sum_{i=1}^{n}\mu(i)*S(n/i)$
非常显然这个东西我们可以结合杜教筛做到每次$O(\sqrt{n})$时间算
总复杂度$O(n^{0.75})$需要卡常_(:зゝ∠)_
#include<cstdio>
#include<cmath>
#define size 4641588
#define mo 1000000007
using namespace std;
int A[2200],mu[size+5],prime[500005];
int v[100005],V[100005],s[100005],S[100005];
//wo you te shu de ka chang ji qiao
bool vis[size+5];
long long n;
int ans,cnt,ny,si;
void pre(){
mu[1]=1;
for(int i=2;i<=size;i++){
if(!vis[i]){vis[i]=true;prime[++cnt]=i;mu[i]=-1;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=size);j++){
int k=prime[j]*i;
vis[k]=true;
if(i%prime[j]==0){mu[k]=0;break;}
else mu[k]=-mu[i];
}
}
}
inline int pow(int x,int k){
int ans=1;
for(;k;k>>=1,x=1LL*x*x%mo)if(k&1)ans=1LL*x*ans%mo;
return ans;
}
inline long long min(long long x,long long y){return x<y?x:y;}
inline int workmu(long long k){
if(k<=size)return mu[k];
if(A[n/k])return A[n/k];
int ans=1;
long long last=k,p=1;
while(true){
long long x=min(last-1,k/(p+1));
ans=(ans-(last-x)%mo*workmu(p))%mo;
if(x==1)break;
last=x;p=k/x;
}
if(ans<0)ans+=mo;A[n/k]=ans;return ans;
}
inline int work(long long k){
if(k<=si)return s[k];
else return S[n/k];
}
inline int workv(long long k){
if(k<=si)return v[k];
else return V[n/k];
}
inline int f(long long k){
int ans=0;
for(int i=1;1LL*i*i<=k;i++){
ans=(ans+1LL*workv(i)*(work(k/i)-work(k/(i+1))))%mo;
if(k/i!=i)ans=(ans+1LL*workv(k/i)*i)%mo;
}
if(ans<0)ans+=mo;
return ans;
}
int main(){
scanf("%lld",&n);si=int(sqrt(n));
pre();
for(int i=2;i<=size;i++)mu[i]+=mu[i-1];ny=pow(2,mo-2);
for(int i=1;i<=si;i++)v[i]=1LL*i*i%mo,V[i]=((n/i)%mo)*((n/i)%mo)%mo,s[i]=1LL*i*(i+1)/2%mo,S[i]=(n/i%mo)*((n/i+1)%mo)%mo*ny%mo;
long long last=n,p=1;
while(true){
long long x=min(last-1,n/(p+1));
if(workmu(last)-workmu(x)!=0)ans=(1LL*(workmu(last)-workmu(x))*f(p)+ans)%mo;
if(x==0)break;
last=x;p=n/last;
}
if(ans<0)ans+=mo;
printf("%d",ans);
}
1238
这个世界充满了套路
$\sum_{d=1}^{n}d\sum_{k=1}^{n/d}\mu(k)k^{2}(S[n/dk])^{2}$
$\sum_{i=1}^{n}(S[n/i])^{2}i\sum_{d|i}\mu(d)*d$
其他一样
也需要卡常_(:зゝ∠)_
#include<cstdio>
#define size 4641588
#define mo 1000000007
using namespace std;
long long n;
int ny,cnt,ans,ny3;
int mu[size+5],prime[400000],A[3000],trick[100005],Trick[100005];
bool vis[size+5];
inline long long min(long long x,long long y){return x<y?x:y;}
inline int sqr(int k){return 1LL*k*k%mo;}
inline int pow(int x,int k){
int ans=1;
for(;k;k>>=1,x=1LL*x*x%mo)if(k&1)ans=1LL*x*ans%mo;
return ans;
}
void pre(){
mu[1]=1;
for(int i=2;i<=size;i++){
if(!vis[i]){prime[++cnt]=i;mu[i]=-1;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=size);j++){
int k=prime[j]*i;
vis[k]=true;
if(i%prime[j]==0){mu[k]=0;break;}
else mu[k]=-mu[i];
}
}
for(int i=2;i<=size;i++)mu[i]=((1LL*mu[i]*i*i+mu[i-1])%mo+mo)%mo;
}
inline int F(long long k){
int t=k%mo;
return 1LL*t*(t+1)%mo*(2*t+1)%mo*ny%mo*ny3%mo;
}
inline int workmu(long long k){
if(k<=size)return mu[k];
if(A[n/k])return A[n/k];
long long last=k,p=1;int ans=1;
while(true){
long long x=min(last-1,k/(p+1));
ans=(ans-1LL*(F(last)-F(x))*workmu(p))%mo;
if(x==1)break;
last=x;p=k/x;
}
if(ans<0)ans+=mo;A[n/k]=ans;
return ans;
}
inline int W(long long k){
if(k==0)return 0;
if(n/k>k)return trick[k];
else return Trick[n/k];
}
inline int f(long long k){
if(k==0)return 0;
int ans=0;
for(int i=1;1LL*i*i<=k;i++){
ans=(ans+1LL*i*workmu(k/i))%mo;
if(k/i!=i)ans=(ans+1LL*(W(k/i)-W(k/(i+1)))*mu[i])%mo;
}
if(ans<0)ans+=mo;
return ans;
}
int main(){
scanf("%lld",&n);
pre();ny=pow(2,mo-2);ny3=pow(3,mo-2);
for(int i=1;1LL*i*i<=n;i++){
trick[i]=1LL*i*(i+1)/2%mo;
int t=(n/i)%mo;
Trick[i]=1LL*t*(t+1)%mo*ny%mo;
}
long long last=n,p=1;int flast=f(last);
while(true){
long long x=min(last-1,n/(p+1));int t=p%mo,fx=f(x);
ans=(ans+1LL*sqr(1LL*(t+1)*t%mo*ny%mo)*(flast-fx))%mo;
if(x==0)break;
flast=fx;last=x;p=n/x;
}
if(ans<0)ans+=mo;
printf("%d\n",ans);
}
1239
模板，为了整齐还是放一下吧
#include<cstdio>
#define mo 1000000007
#define size 4641588
using namespace std;
int cnt,ny;
long long n;
long long A[3000],phi[size+5];
int prime[500005];
inline int pow(int x,int k){
int ans=1;
for(;k;k>>=1,x=1LL*x*x%mo)if(k&1)ans=1LL*x*ans%mo;
return ans;
}
void pre(){
phi[1]=1;
for(int i=2;i<=size;i++){
if(!phi[i]){prime[++cnt]=i;phi[i]=i-1;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=size);j++){
int k=prime[j]*i;
if(i%prime[j]==0){phi[k]=phi[i]*prime[j];break;}
else phi[k]=phi[i]*(prime[j]-1);
}
}
for(int i=2;i<=size;i++)phi[i]=(phi[i]+phi[i-1])%mo;ny=pow(2,mo-2);
}
inline long long min(long long x,long long y){return x<y?x:y;}
inline int work(long long k){
if(k<=size)return phi[k];
if(A[n/k])return A[n/k];
int t=k%mo;
int ans=1LL*t*(t+1)%mo*ny%mo;
long long last=k,p=1;
while(true){
long long x=min(last-1,k/(p+1));
ans=(ans-(last-x)%mo*work(p))%mo;
if(x==1)break;
last=x;p=k/x;
}
if(ans<0)ans+=mo;A[n/k]=ans;
return ans;
}
int main(){
scanf("%lld",&n);
pre();
printf("%d",work(n));
}
1244
同模板
#include<cstdio>
#define mo 1000000007
#define size 4641588
using namespace std;
int cnt,ny;
long long n;
long long A[3000],phi[size+5];
int prime[500005];
inline int pow(int x,int k){
int ans=1;
for(;k;k>>=1,x=1LL*x*x%mo)if(k&1)ans=1LL*x*ans%mo;
return ans;
}
void pre(){
phi[1]=1;
for(int i=2;i<=size;i++){
if(!phi[i]){prime[++cnt]=i;phi[i]=i-1;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=size);j++){
int k=prime[j]*i;
if(i%prime[j]==0){phi[k]=phi[i]*prime[j];break;}
else phi[k]=phi[i]*(prime[j]-1);
}
}
for(int i=2;i<=size;i++)phi[i]=(phi[i]+phi[i-1])%mo;ny=pow(2,mo-2);
}
inline long long min(long long x,long long y){return x<y?x:y;}
inline int work(long long k){
if(k<=size)return phi[k];
if(A[n/k])return A[n/k];
int t=k%mo;
int ans=1LL*t*(t+1)%mo*ny%mo;
long long last=k,p=1;
while(true){
long long x=min(last-1,k/(p+1));
ans=(ans-(last-x)%mo*work(p))%mo;
if(x==1)break;
last=x;p=k/x;
}
if(ans<0)ans+=mo;A[n/k]=ans;
return ans;
}
int main(){
scanf("%lld",&n);
pre();
printf("%d",work(n));
}
1220
终于不是套路了
我们先证一个结论
$d(n*m)=\sum_{i|n}\sum_{j|m}n/i*j*e(gcd(i,j))$
考虑单个素数对答案的贡献，设$n=N*p^{a}$,$m=M*p^{b}$
$d(n*m)=d(N*M)*d(p^{a+b})=d(N*M)*(1+p+...+p^{a+b-1}+p^{a+b})$
$\sum_{i|p^{a}}\sum_{j|p^{b}}n/i*j*e(gcd(i,j))=1+p+...+p^{a+b-1}+p^{a+b}$
简单归纳一下就可以得到那个结论
其实我是从BZOJ3994想到的
$\sum_{i=1}^{n}\sum_{j=1}^{n}d(i*j)=\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{a|i}\sum_{b|j}i/a*b*e(gcd(a,b))$
$\sum_{i=1}^{n}\sum_{j=1}^{n}S(n/i)*j*[n/j]*e(gcd(i,j))$
$\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{n/d}S(n/i/d)\sum_{j=1}^{n/d}j*d*[n/j/d]$
$\sum_{d=1}^{n}\mu(d)d(\sum_{i=1}^{n/d}[n/d/i])^{2}$
因为套路题磨练出的卡常技巧好像跑得很快_(:зゝ∠)_
#include<cstdio>
#define mo 1000000007
#define m 1000000
using namespace std;
int mu[m+5],prime[100005];
int n,ans,cnt;
int A[1005];
bool vis[m+5];
void pre(){
mu[1]=1;
for(int i=2;i<=m;i++){
if(!vis[i]){prime[++cnt]=i;mu[i]=-1;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=m);j++){
int k=prime[j]*i;
vis[k]=true;
if(i%prime[j]==0){mu[k]=0;break;}
else mu[k]=-mu[i];
}
}
for(int i=2;i<=m;i++){
mu[i]=mu[i]*i+mu[i-1];
if(mu[i]<0)mu[i]+=mo;
if(mu[i]>=mo)mu[i]-=mo;
}
}
inline int min(int x,int y){return x<y?x:y;}
inline int f(int k){
int last=k,p=1,ans=0;
for(int i=1;i*i<=k;i++){
ans=(ans+1LL*i*(i+1)/2*(k/i-k/(i+1)))%mo;
if(k/i!=i)ans=(ans+1LL*(k/i)*(k/i+1)/2)%mo;
}
return 1LL*ans*ans%mo;
}
inline int workmu(int k){
if(k<=m)return mu[k];
if(A[n/k])return A[n/k];
int ans=1;
for(int i=1;i*i<=k;i++){
if((i>1)&&(k/i!=i))ans=(ans-1LL*workmu(k/i)*i)%mo;
ans=(ans-1LL*(k/i+k/(i+1)+1)*(k/i-k/(i+1))/2%mo*mu[i])%mo;
}
if(ans<0)ans+=mo;A[n/k]=ans;
return ans;
}
int main(){
scanf("%d",&n);
pre();
int last=n,p=1;
while(true){
int x=min(last-1,n/(p+1));
ans=(ans+1LL*(workmu(last)-workmu(x))*f(p))%mo;
if(x==0)break;
last=x;p=n/x;
}
if(ans<0)ans+=mo;
printf("%d",ans);
}
1223
假设$gcd(x,y)=d,x=ad,y=bd,x<y$
$\frac{1}{ad}+\frac{1}{bd}=\frac{a+b}{abd}$
因为a,b互质所以非常显然a+b和a互质,a+b和b互质，所以a+b和ab互质
所以d能被a+b整除，同时要满足$bd<=n$
$\sum_{a=1}^{n}\sum_{b=a+1}^{n}e(gcd(a,b))*n/(a+b)/b$
$\sum_{d=1}^{n}\mu(d)\sum_{b=2}^{n/d}\sum_{a=1}^{b-1}[n/(a+b)/b]$
显然实际枚举的时候b大于$\sqrt{n}$对答案没有贡献，对a的枚举也一样，然后就可以显著地减少枚举，O(跑得过)
#include<cstdio>
#include<cmath>
using namespace std;
long long n,ans;
int cnt,size,last,s;
int mu[400005],prime[30005];
bool vis[400005];
inline long long min(long long x,long long y){return x<y?x:y;}
void pre(){
mu[1]=1;
for(int i=2;i<=size;i++){
if(!vis[i]){prime[++cnt]=i;mu[i]=-1;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=size);j++){
int k=prime[j]*i;
vis[k]=true;
if(i%prime[j]==0){mu[k]=0;break;}
else mu[k]=-mu[i];
}
}
}
inline long long f(long long s,int l,int r){
long long ans=0;
if(r>s)r=s;
int last=r;
long long p=s/r;
while(true){
int x=min(last-1,s/(p+1));
if(x<l){ans+=p*(last-l+1);break;}
ans+=p*(last-x);
last=x;p=s/x;
}
return ans;
}
inline int long long work(long long p){
long long ans=0;
for(int i=2;1LL*i*(i+1)<=p;i++)ans+=f(p/i,i+1,2*i-1);
return ans;
}
int main(){
scanf("%lld",&n);
size=int(sqrt(n));
pre();last=-1;
for(int i=1;i<=size;i++)if(mu[i])ans+=mu[i]*work(n/i/i);
printf("%lld",ans);
}
1602
非常显然x就是$\mu(i)$因为$\sum_{d|i}\mu(d)=e(i)$
问题变成了求$\mu(i)=x$的第k小解
考虑二分答案，$\sum_{i=1}^{n}\mu(i)$可以杜教筛，我们考虑$\sum_{i=1}^{n}|\mu(i)|$
$\sum_{i=1}^{n}\left | \mu(i)\right |$可以洲爷筛，但是太慢了我们不能接受。
简单地容斥一下可以发现$\sum_{i=1}^{n}|\mu(i)|=\sum_{i=1}^{\sqrt{n}}[n/i^{2}]*\mu(i)$
$\sum_{i=1}^{n}|\mu(i)|=\sum_{i=1}^{\sqrt{n}}[n/i^{2}]*\mu(i)$我们就可以直接暴力在$O(\sqrt{n})$的时间内算出
设$ans1=\sum_{i=1}^{n}\mu(i)$,$ans2=\sum_{i=1}^{n}\left | \mu(i)\right |$
那么$\sum_{i=1}^{n}|\mu(i)=0|=n-ans2$
$\sum_{i=1}^{n}|\mu(i) =1|=\frac{ans1+ans2}{2}$
$\sum_{i=1}^{n}|\mu(i) =-1|=\frac{ans2-ans1}{2}$
注意因为要多次杜教筛所以杜教筛的m适当开大会比较好面向数据调参大约5000W-7000W会比较好。
调参之后还是过不了就要像我一样分段打表减少二分上下界_(:зゝ∠)_
#include<cstdio>
#include<algorithm>
#define m 70000000
using namespace std;
int mu[m+5],p,cnt;
long long o,n;
int a[2005];
long long t[2005];
long long table0[]={0,98696539ll,197390590ll,296090773ll,394785811ll,493478717ll,592174619ll,690865539ll,789573419ll,888269506ll,986963617ll,1085638187ll,1184353249ll,1283058453ll,1381753534ll,1480438790ll,1579123499ll,1677833470ll,1776525191ll,1875223162ll,1973931083ll,2072625209ll,2171327727ll,2270010614ll,2368701689ll,2467400871ll,2566083487ll,2664774382ll,2763486298ll,2862171758ll,2960878366ll,3059601391ll,3158288941ll,3256989389ll,3355689863ll,3454377809ll,3553053738ll,3651737802ll,3750418478ll,3849108369ll,3947816126ll,4046541778ll,4145229385ll,4243939458ll,4342618289ll,4441315945ll,4540020235ll,4638728678ll,4737406890ll,4836101882ll,4934800549ll,5033493691ll,5132213873ll,5230910298ll,5329603785ll,5428313846ll,5527000218ll,5625677806ll,5724366653ll,5823061145ll,5921763357ll,6020450645ll,6119140105ll,6217818269ll,6316515511ll,6415221166ll,6513923318ll,6612592645ll,6711292427ll,6809993799ll,6908712746ll,7007411354ll,7106109843ll,7204816138ll,7303529521ll,7402221537ll,7500928390ll,7599639885ll,7698355851ll,7797058563ll,7895737187ll,7994415551ll,8093084541ll,8191784013ll,8290456598ll,8389140990ll,8487847905ll,8586540758ll,8685256349ll,8783960642ll,8882642026ll,8981338753ll,9080028929ll,9178727618ll,9277421983ll,9376117705ll,9474818718ll,9573507146ll,9672186455ll,9770872962ll,9869555098ll,9968249813ll,10000000001ll};
long long table1[]={0,76516436ll,153032768ll,229549144ll,306065450ll,382581992ll,459098343ll,535614471ll,612131050ll,688647396ll,765163884ll,841680268ll,918196704ll,994713003ll,1071229320ll,1147745600ll,1224262084ll,1300778556ll,1377294908ll,1453811249ll,1530327700ll,1606844004ll,1683360388ll,1759876625ll,1836393076ll,1912909668ll,1989426024ll,2065942540ll,2142458912ll,2218975339ll,2295491616ll,2372007816ll,2448524196ll,2525040650ll,2601557060ll,2678073327ll,2754589864ll,2831106220ll,2907622467ll,2984138991ll,3060655493ll,3137171884ll,3213688131ll,3290204276ll,3366720488ll,3443236892ll,3519753282ll,3596269536ll,3672785943ll,3749302512ll,3825819100ll,3902335533ll,3978851916ll,4055368248ll,4131884655ll,4208400882ll,4284917544ll,4361433950ll,4437950319ll,4514466904ll,4590983132ll,4667499567ll,4744016032ll,4820532561ll,4897048888ll,4973565245ll,5050081532ll,5126597800ll,5203114182ll,5279630542ll,5356146906ll,5432663284ll,5509179460ll,5585695920ll,5662212272ll,5738728698ll,5815244964ll,5891761360ll,5968277916ll,6044794209ll,6121310832ll,6197827338ll,6274343648ll,6350859850ll,6427376220ll,6503892598ll,6580408772ll,6656925240ll,6733441548ll,6809957936ll,6886474320ll,6962990778ll,7039507145ll,7116023466ll,7192539908ll,7269056127ll,7345572664ll,7422089041ll,7498605338ll,7575121755ll,7651638261ll,7728154632ll,7804671039ll,7881187707ll,7957703888ll,8034220149ll,8110736448ll,8187252916ll,8263769248ll,8340285728ll,8416802132ll,8493318525ll,8569835043ll,8646351180ll,8722867615ll,8799383988ll,8875900375ll,8952416780ll,9028933112ll,9105449301ll,9181965652ll,9258482256ll,9334998621ll,9411515184ll,9488031604ll,9564547850ll,9641064416ll,9717580728ll,9794097112ll,9870613308ll,9947129778ll,10000000001ll};
long long table2[]={0,98695734ll,197393759ll,296085470ll,394782419ll,493481806ll,592178047ll,690879445ll,789563222ll,888259434ll,986957195ll,1085675215ll,1184352063ll,1283038665ll,1381735834ll,1480442462ll,1579149706ll,1677832129ll,1776532638ll,1875226555ll,1973910394ll,2072608571ll,2171298219ll,2270007230ll,2368708266ll,2467401414ll,2566110963ll,2664812038ll,2763492203ll,2862198649ll,2960884319ll,3059552974ll,3158257565ll,3256949471ll,3355641371ll,3454345331ll,3553061986ll,3651769934ll,3750480703ll,3849182731ll,3947866995ll,4046533977ll,4145238465ll,4243920370ll,4342633341ll,4441327994ll,4540015657ll,4638698898ll,4737412873ll,4836109691ll,4934803611ll,5033502835ll,5132174195ll,5230870181ll,5329569021ll,5428251282ll,5526957066ll,5625671179ll,5724374574ll,5823072237ll,5921761942ll,6020466854ll,6119169254ll,6217883243ll,6316577914ll,6415264831ll,6513954815ll,6612677638ll,6711369549ll,6810060517ll,6908733565ll,7007427273ll,7106120474ll,7204806518ll,7303485191ll,7402185281ll,7500869947ll,7599550649ll,7698226571ll,7796916119ll,7895629382ll,7994343758ll,8093066557ll,8191759205ll,8290478699ll,8389186818ll,8487871827ll,8586570670ll,8685247539ll,8783935197ll,8882645819ll,8981341241ll,9080043461ll,9178737087ll,9277434545ll,9376130469ll,9474821742ll,9573525386ll,9672238317ll,9770943295ll,9869652770ll,9968351223ll,10000000001ll};
int prime[5000000];
bool vis[m+5];
inline int workmu(long long k){
if(k<=m)return mu[k];
if(t[o/k]==o)return a[o/k];
int ans=1;
for(int i=1;k/i>=i;i++){
if(i>1)ans-=workmu(k/i);
if(k/i!=i)ans-=mu[i]*(k/i-k/(i+1));
}
t[o/k]=o;a[o/k]=ans;
return ans;
}
inline long long workMu(long long k){
long long ans=0;
for(int i=1;1LL*i*i<=k;i++)ans+=(k/i/i)*(mu[i]-mu[i-1]);
return ans;
}
void pre(){
mu[1]=1;
for(int i=2;i<=m;i++){
if(!vis[i]){prime[++cnt]=i;mu[i]=-1;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=m);j++){
int k=prime[j]*i;
vis[k]=true;
if(i%prime[j]==0){mu[k]=0;break;}
else mu[k]=-mu[i];
}
}
for(int i=1;i<=m;i++)mu[i]+=mu[i-1];
}
inline long long check(long long mid,int p){
o=mid;
long long ans1=workMu(o),ans2=workmu(o);
if(p==0)return o-ans1;
else if(p==1)return (ans1+ans2)/2;
else return (ans1-ans2)/2;
}
int main(){
scanf("%d%I64d",&p,&n);
pre();
long long l,r;
if(p==-1)l=table0[(n-1)/30000000],r=table0[(n-1)/30000000+1];
if(p==0)l=table1[(n-1)/30000000],r=table1[(n-1)/30000000+1];
if(p==1)l=table2[(n-1)/30000000],r=table2[(n-1)/30000000+1];
while(r-l>1){
long long mid=(l+r)>>1;
if(check(mid,p)>=n)r=mid;
else l=mid;
}
printf("%I64d\n",r);
}
1584
因为自己太傻了看不懂题解只好自己YY...
1220的思路,$\sigma (i*j)=\sum_{a|i}\sum_{b|j}i/a*b*e(gcd(a,b))$
$\sum_{i=1}^{n}\sum_{j=1}^{n}max(i,j)\sum_{a|i}\sum_{b|j}i/a*b\sum_{d|(a,b)}\mu(d)$
$\sum_{i=1}^{n}\sum_{j=1}^{n}max(i,j)\sum_{d|(i,j)}\mu(d)\sum_{a|\frac{i}{d}}\sum_{b|\frac{j}{d}}i/a*b$
$\sum_{i=1}^{n}\sum_{j=1}^{n}max(i,j)\sum_{d|(i,j)}\mu(d)d\sum_{a|\frac{i}{d}}\sum_{b|\frac{j}{d}}a*b$
$\sum_{d=1}^{n}\mu(d)d^{2}\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}max(i,j)\sigma(i)\sigma(j)$
$\mu(d)d^{2}$的前缀和我们可以线性筛，后面那个东西线性筛处理出约数和之后瞎搞一下也很好搞出来。
现在我们的问题变成了求$\sum_{i=1}^{n}\sum_{d|i}g(d)*f(i/d)$的形式，假如f和g函数都是积性函数的话这个函数也是积性函数。
但是很遗憾后面那坨东西并不是积性函数_(:зゝ∠)_
然后我在那边写$O(T\sqrt{n})$写了半天，我卡到1.2s还以为是自己被卡常了_(:зゝ∠)_
然而这个东西是可以$O(nlog)$预处理的，只要对于每一个i，枚举一个j,i*j<=n,ans[i*j]+=g(i)*f(j)就可以了_(:зゝ∠)_
每次询问O(1)
#include<cstdio>
#include<ctime>
#define mo 1000000007
using namespace std;
int f[1000005],prime[100005],mu[1000005],last[1000005],s[1000005],ans[1000005];
int cnt,n,test;
inline int read(){
int ret=0;
char c=getchar();
while((c>'9')||(c<'0'))c=getchar();
while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ret;
}
void pre(){
mu[1]=1;f[1]=1;
for(int i=2;i<=1000000;i++){
if(!last[i]){last[i]=1;s[i]=i+1;mu[i]=-1;prime[++cnt]=i;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=1000000);j++){
int k=prime[j]*i;
if(i%prime[j]==0){s[k]=s[i]*prime[j]+1,last[k]=last[i],mu[k]=0;break;}
else s[k]=prime[j]+1,last[k]=i,mu[k]=-mu[i];
}
}
for(int i=2;i<=1000000;i++)f[i]=f[last[i]]*s[i],mu[i]=1LL*mu[i]*i*i%mo;
int s=1;
for(int i=2;i<=1000000;i++){
s=(s+f[i])%mo;
f[i]=1LL*((s<<1)-f[i])*f[i]%mo*i%mo;
}
for(int i=1;i<=1000000;i++)
for(int j=1;j*i<=1000000;j++)ans[i*j]=(ans[i*j]+1LL*f[i]*mu[j])%mo;
for(int i=2;i<=1000000;i++)ans[i]=(ans[i]+1LL*ans[i-1]+mo)%mo;
}
int main(){
pre();
test=read();
for(int I=1;I<=test;I++)printf("Case #%d: %d\n",I,ans[read()]);
}
2016年8月19日 19:11
黄比利真是太强啦
2022年9月14日 17:35
We advised contacting your Telugu teacher to get a chapter-wise practice model question paper for both levels of exams held under the school or board level and follow the link to download All AP SSC 10th Class Telugu Model Question Papers 2023 with Solutions. Every student everyone can download AP 10th Telugu Model Paper 2023 chapter-wise for paper-1, paper-2 exam theory, objective, AP SSC Telugu Model Paper multiple-choice questions (MCQ), Bit Question Bank with practice study material with IMP Question paper pdf with old scheme suggestions for AP 10th Class students 2023 to the Telugu Subject.