洛谷 P10584 [蓝桥杯 2024 国 A] 数学题（整除分块+杜教筛）

题目

思路来源

登录 - Luogu Spilopelia

题解

参考了两篇洛谷题解，第一篇能得出这个式子，第二篇有比较严格的复杂度分析

结合去年蓝桥杯洛谷P9238，基本就能得出这题的正确做法

代码

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<map>
#include<unordered_map>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e7+10;
bool ok[N];
int pr[N/10],mu[N],ans[N],cnt,up;
unordered_map<int,int>smu;
unordered_map<ll,ll>smu2;
ll n,m;
void sieve(ll n){mu[1]=1;ans[1]=1;for(ll i=2;i<N;++i){if(!ok[i]){pr[cnt++]=i;mu[i]=-1;}for(int j=0;j<cnt;++j){ll k=i*pr[j];if(k>=N)break;ok[k]=1;if(i%pr[j]==0){mu[k]=0;break; }mu[k]=-mu[i];}ans[i]+=ans[i-1]+(mu[i]!=0);mu[i]+=mu[i-1];}
}
int djsmu(int n){if(n<N)return mu[n];if(smu.count(n))return smu[n];int ans=1;for(int l=2,r;l<=n;l=r+1){r=n/(n/l);ans=ans-(r-l+1)*djsmu(n/l);}return smu[n]=ans;
}
ll cal(ll n){if(n<N)return ans[n];if(smu2.count(n))return smu2[n];ll res=0;for(ll l=1,r,v;l*l<=n;l=r+1){v=n/l/l;r=sqrt(n/v);res+=v*(djsmu(r)-djsmu(l-1));}return smu2[n]=res;
}
int main(){cin>>n>>m;sieve(n);ull ans=0;for(ll l=1,r,x,y;l<=min(n,m);l=r+1){x=sqrt(n/l),y=sqrt(m/l);r=min(n/(x*x),m/(y*y));ans+=1ull*(cal(r)-cal(l-1))*x*y;}cout<<ans<<endl;return 0;
}