\({\color{Orange}\star}\) 2024-03-24 \({\color{Orange}\star}\)
完全平方数
题意就是求出第 \(k\) 个不是完全平方数的倍数的数
随着数 \(n\) 的增加 \([1,n]\) 的满足条件的数的个数是单调不降的
可以二分 \(n\) 的值，然后算出 \([1,n]\) 中满足条件的数的个数，根据它与 \(k\) 的关系调整左右边界
然后考虑如何快速算出 \([1,n]\) 中不是完全平方数的倍数的数的个数
其实就是 \(n\) 减去 \([1,n]\) 中 是 完全平方数的倍数的数的个数
发现当我们筛掉了一个数的平方的所有倍数的时候，这个数的所有倍数的平方的倍数就已经被筛掉了
因此只考虑质数的平方的倍数就行了
- 在 \(n\) 个数中减去 \(\sum_{p是质数}\lfloor\frac{n}{p^2}\rfloor\)
发现这样的话两个质数乘积的平方的倍数就被重复去掉了，再加回来
- 再加上 \(\sum_{p,q是质数}\lfloor\frac{n}{(pq)^2}\rfloor\)
……
发现如果一个数 \(x\) ：
- 他有平方因子，那么不用管他
- 他本质不同的质因子的个数是奇数 要减去 \(\lfloor\frac{n}{x^2}\rfloor\)
- 他本质不同的质因子的个数是偶数 要加上 \(\lfloor\frac{n}{x^2}\rfloor\)
这个容斥系数正好就是 莫比乌斯函数 啊
得出结论：
\([1,n]\) 范围内的 不是完全平方数的倍数的数 的个数为
\[\sum_{i}^{\lfloor\sqrt{n}\rfloor}\mu(i)\left\lfloor\frac{n}{i^2}\right\rfloor \]\(i\) 到 \(\sqrt{n}\) 的原因是再大后面的值就都是 \(0\) 了
第 \(10^9\) 个符合条件的数是 \(1644934081\) 因此 mobius函数 求到第 \(\left\lceil\sqrt{1644934081}\right\rceil=40558\) 个
CODE:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=40600;//40558
int K;
int primes[N],cntp;
bool st[N];
int mu[N];
void init_mu() {
mu[1]=1;
for(int i=2;i<=40560;i++) {
if(!st[i]) {
primes[++cntp]=i;
mu[i]=-1;
}
for(int j=1;i*primes[j]<=40560;j++) {
st[i*primes[j]]=true;
if(i%primes[j]==0) {
mu[i*primes[j]]=0;
break;
}
mu[i*primes[j]]=-mu[i];
}
}
}
int calc(ll n) {
int res=0;
for(int i=1;i<=(int)sqrt(n);i++) res+=mu[i]*(n/(i*i));
return res;
}
int main() {
init_mu();
int T;
scanf("%d",&T);
while(T--) {
scanf("%d",&K);
ll lft=0,rgh=1644934081,ans;
while(lft<rgh) {
ll mid=lft+rgh+1>>1;
if(calc(mid)>=K) ans=mid,rgh=mid-1;
else lft=mid;
}
printf("%lld\n",ans);
}
return 0;
}
第 38 行，
sqrt(x)返回的是浮点型，转成int再和i比较，不然会死循环
看了一下模拟赛
15min 切了 T1
haosen 秒切 T4 ，我给写了
T2 会，但是半道开始就剩 15min 了，不写了
T3 没看，周日大好时光不能浪费，溜了
看了一道数学题，中午回去想想吧
樱花
\({\color{Chocolate}题意}\)
求方程：
的正整数解的组数，答案对 \(10^9+7\) 取模
\({\color{Chocolate}题解}\)
\[\because\frac{1}{x}+\frac{1}{y}=\frac{1}{n!} \ \ \ x,y>0 \]\[\therefore\frac{1}{x},\frac{1}{y}<\frac{1}{n!} \]\[\therefore x,y>n! \]设 \(x=n!+p,y=n!+q \ \ \ p,q>0\)
（这一步的转化好像挺常见的，要记住）
原式化为
\[\frac{1}{n!+p}+\frac{1}{n!+q}=\frac{1}{n} \]化简得
\[(n!)^2=pq \]原题转化为求 \((n!)^2\) 的正约数个数
若 \(x=\sum_{i=1}^{k}{p_k}^{\alpha_k}\)
则 \(x\) 的约数个数是 \(\prod_{i=1}^{k}(\alpha_i+1)\)
直接朴素分解质因数的话是 \(O(n\sqrt{n})\) 的，\(10^6\) 的数据过不了
ztx 大佬教我 \(O(log n)\) 分解质因数：
- 线性筛的时候可以求出来每个数的最小质因子是多少
- 由于质因子最小是 \(2\)，每次除完至少减少一半，时间复杂度 \(O(\log n)\)
总的时间复杂度 \(O(n\log n)\)
记得是 \((n!)^2\) 统计质因子个数的时候 \(+2\)
\({\color{Chocolate}代码}\)
#include<iostream>
#include<cstring>
#include<algorithm>
#define mod 1000000007
using namespace std;
const int N=1e6+100;
int primes[N],cntp;
bool st[N];
int minpr[N];
void init_p(int x) {
for(int i=2;i<=x;i++) {
if(!st[i]) primes[++cntp]=i,minpr[i]=i;
for(int j=1;i*primes[j]<=x;j++) {
st[i*primes[j]]=true;
minpr[i*primes[j]]=primes[j];
if(i%primes[j]==0) break;
}
}
}
int n;
int cntfctr[N];
int main() {
scanf("%d",&n);
init_p(1e6+10);
int mx=0;
for(int i=1;i<=n;i++) {
int x=i;
while(x>1) {
mx=max(mx,minpr[x]);
cntfctr[minpr[x]]+=2;
x/=minpr[x];
}
}
long long ans=1;
for(int i=1;primes[i]<=mx;i++) ans=(ans*(cntfctr[primes[i]]+1ll))%mod;
printf("%lld\n",ans);
return 0;
}