为了让自己看起来有点事干 ，做个套题吧。。不然老是东翻翻西翻翻也不知道在干嘛。。。
(f 3309: DZY Loves Math)
令 (h=f*mu)
很明显题目要求的就是$$sum_{i=1}^{min(n,m)}h(i) cdot left lfloor frac{n}{i}
ight
floor left lfloor frac{m}{i}
ight
floor$$
那个 (*) 就是狄利克雷卷积，虽然说我也不知道是不是这么写。。
然后我就不会了，这个卷出来又不是积性函数咋搞啊，暴力筛肯定T啊。。
然后通过奇奇妙妙的方法可以发现 (h((p_1p_2 cdots p_k)^t)=(-1)^k)，否则为 (0) 。大佬说随便分析一下就出来了，反正我是分析不出来，半懂不懂。。作为一个不负责任的博主当然就随便挂个链接。。
然后就阔以线性筛+前缀和预处理，询问分个块就完了。
#include<bits/stdc++.h>
#define LL long long
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define rf(i,x,y) for(int i=(x);i>=(y);i--)
#define frl(i,x,y) for(int i=(x);i<(y);i++)
using namespace std;
const int N=10000001;
int b[N],p[N/10],L,c[N],a[N],h[N];
int T,n,m;
void read(int &x){
char ch=getchar();x=0;
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}
void init(){
//h[1]=1;
frl(i,2,N){
if (!b[i]) p[++L]=i,a[i]=i,c[i]=1,h[i]=1;
for(int j=1;i*p[j]<N;j++){
int x=i*p[j];
b[x]=1;
if (i%p[j]==0){
a[x]=a[i]*p[j];c[x]=c[i]+1;
if (i==a[i]) h[x]=1;
else h[x]=c[i/a[i]]==c[x]?-h[i/a[i]]:0;
break;
}
c[x]=1;a[x]=p[j];
h[x]=c[i]==1?-h[i]:0;
}
}
frl(i,2,N) h[i]+=h[i-1];
}
int main(){
init();
read(T);
while(T--){
read(n);read(m);
LL ans=0;
int pre=0;int p=1;
while(p<=n&&p<=m){
if (n/(n/p)<m/(m/p)) p=n/(n/p);
else p=m/(m/p);
ans+=1LL*(h[p]-h[pre])*(n/p)*(m/p);
pre=p;p++;
}
printf("%lld
",ans);
}
return 0;
}
(f 3309: DZY Loves Math II)
别的部分都很好想，但是那个背包的部分简直神仙吧。。
我懒得写一遍题解，这篇题解让我最终看懂了QAQ
（你懒还有理了）
顺便，进本题第一页祭，合影留念QwQ
感觉啥也没优化啊？？发生了啥？？？（也许是取模优化？不过我日常取模优化，只是因为感觉这样写更方便。。）
#include<bits/stdc++.h>
#define LL long long
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define rf(i,x,y) for(int i=(x);i>=(y);i--)
#define frl(i,x,y) for(int i=(x);i<(y);i++)
using namespace std;
const int N=2000002;
const int p=1e9+7;
int S,q,m,ss;
LL n;
int d[10],L;
int f[N*7];
int inv;
void read(int &x){
char ch=getchar();x=0;
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}
void read(LL &x){
char ch=getchar();x=0;
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}
inline void Add(int &x,int y){
x+=y;
while(x<0) x+=p;
while(x>=p) x-=p;
}
int qpow(int a,int n){
LL ans=1;
for(LL sum=a;n;n>>=1,sum=sum*sum%p) if (n&1) ans=ans*sum%p;
return ans;
}
void init(){
int x=S;
for(int i=2;i*i<=x;i++)
if (x%i==0){
x/=i;d[++L]=i;ss+=i;
if (x%i==0){
fr(i,1,q) printf("0
");
exit(0);
}
}
if (x>1) d[++L]=x,ss+=x;
m=S*L;
f[0]=1;
fr(i,1,L){
fr(j,d[i],m) Add(f[j],f[j-d[i]]);
rf(j,m,S) Add(f[j],-f[j-S]);
}
inv=1;frl(i,2,L) inv*=i;inv=qpow(inv,p-2);
}
inline int C(LL x){
LL ans=inv;
frl(i,0,L-1) ans=ans*((x-i)%p)%p;
//cout<<ans<<endl;
return ans;
}
int main(){
read(S);read(q);
init();
while(q--){
read(n);
if (n<ss){ printf("0
");continue; }
n-=ss;
LL x=n/S;
int ans=0;
for(LL i=x;n-i*S<=m;i--)
Add(ans,1LL*C(i+L-1)*f[n-i*S]%p);
printf("%d
",ans);
}
return 0;
}
/*
30 1
1000000000000000000
*/