\({\color{orange}\star}\) 2024-03-22 \({\color{orange}\star}\)
模积和
# 题目描述 #
求
\[\sum_{i=1}^{n} \sum_{j=1}^{m} (n \bmod i) \times (m \bmod j), i \neq j \]\(\bmod 19940417\) 的值
# Solution #
不妨设 \(n\le m\)
容斥原理
\[\sum_{i=1}^{n} \sum_{j=1}^{m} (n \bmod i) \times (m \bmod j), i \neq j \newline \]\[=\sum_{i=1}^n\sum_{j=1}^m(n\bmod i)\times(m\bmod j)-\sum_{i=1}^n(n\bmod i)(m\bmod i) \]两个和式拆开计算
数论分块
用于计算形如
的和式
其中 \(f(i)\) 可以快速求出区间和
当 \(i\) 从 \(1\) 取到 \(n\) 时，\(\left\lfloor\frac{n}{i}\right\rfloor\) 的取值不超过 \(2\sqrt{n}\) 种（证明 见 OI-Wiki）
这样我们就可以把 \(\left\lfloor\frac{n}{i}\right\rfloor\) 取值相同的区间放到一起处理
\(i\) 所在的区间的右端点为 \(\left\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\right\rfloor\)
拆成五个部分用数论分块
时间复杂度 \(O(\sqrt{n})\)
#include<iostream>
#include<cstring>
#include<algorithm>
#define mod 19940417
using namespace std;
typedef long long ll;
const ll inv2=9970209,inv6=3323403;
ll n,m;
ll calc1(ll x) {
ll l=1,r,res=0;
while(l<=x) {
r=min(x/(x/l),x);
res=(res+(l+r)*(r-l+1)%mod*inv2%mod*(x/l)%mod)%mod;
l=r+1;
}
return res;
}
ll calc2(ll x,ll y) {
ll l=1,r,res=0;
while(l<=n) {
r=min(y/(y/l),n);
res=(res+x*(l+r)%mod*(r-l+1)%mod*inv2%mod*(y/l)%mod)%mod;
l=r+1;
}
return res;
}
ll calc3() {
ll l=1,r,res=0;
while(l<=n) {
r=min(n,min(n/(n/l),m/(m/l)));
res=(res+((r*(r+1)%mod*(2*r%mod+1)%mod-(l-1)*l%mod*(2*l%mod-1)%mod)%mod+mod)%mod*inv6%mod*(n/l)%mod*(m/l)%mod)%mod;
l=r+1;
}
return res;
}
int main() {
scanf("%lld%lld",&n,&m);
if(n>m) swap(n,m);
ll A=((n*n%mod-calc1(n))%mod+mod)%mod,B=((m*m%mod-calc1(m))%mod+mod)%mod;
ll ans=((A*B%mod-n*n%mod*m%mod)%mod+mod)%mod;
ll C=calc2(m,n),D=calc2(n,m);
ans=((ans+C)%mod+D)%mod;
ll E=calc3();
ans=((ans-E)%mod+mod)%mod;
printf("%lld\n",ans);
return 0;
}
tips:
- \(a\bmod b\) 有时候可以转化为 \(a-\left\lfloor\frac{a}{b}\right\rfloor\times b\)
- \(\sum_{i=1}^k i^2=\frac{k(k+1)(2k+1)}{6}\)
- 所有的运算都要取模！
礼物
准备学 exLucas
结果学长们说 exLucas 不用学，没用
那就不做这题了
但是看懂了 Lucas 的证明，也算有点收获吧
聪明的燕姿
# 题意 #
求所有 所有约数的和 为 \(S\) 的数
唯一分解定理：
\[x=\prod_{i=1}^k{p_i}^{\alpha_i} \]一个数的所有约数的和：
\[s=\prod_{i=1}^k(\sum_{j=0}^{\alpha_i}{p_i}^j) \]然后暴搜就行了
s 表示当前还能搜多少，k 表示 当前从第 k 个质数开始枚举（保证质数从小到大），w 表示当前的数是多少
- 枚举上限：因为从小到大， \((p_i+1)^2<(p_i+1)(p_j+1)\le s\)
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100005;
ll S;
ll primes[N],cntp;
bool st[N];
void initp() {
st[0]=st[1]=true;
for(ll i=2;i<=100000;i++) {
if(!st[i]) primes[++cntp]=i;
for(ll j=1;i*primes[j]<=100000;j++) {
st[i*primes[j]]=true;
if(i%primes[j]==0) break;
}
}
}
ll ans[N],cnta;
bool isp(int x) {
if(x<2) return false;
for(int i=2;i*i<=x;i++) if(x%i==0) return false;
return true;
}
void dfs(ll s,ll k,ll w) {
if(s==1) {
ans[++cnta]=w;
return;
}
if(isp(s-1)&&s>primes[k]) ans[++cnta]=w*(s-1);
for(ll i=k;primes[i]*primes[i]<=s;i++) {
ll pw=primes[i],sm=primes[i]+1;
while(sm<=s) {
if(s%sm==0) dfs(s/sm,i+1,w*pw);
pw*=primes[i];
sm+=pw;
}
}
}
int main() {
initp();
while(scanf("%lld",&S)!=EOF) {
cnta=0;
dfs(S,1,1);
sort(ans+1,ans+cnta+1);
printf("%lld\n",cnta);
for(int i=1;i<=cnta;i++) printf("%lld ",ans[i]);
if(cnta) puts("");
}
return 0;
}
圆上的整点
看题解区有一个视频，看了半个小时讲的复数高斯素数啥的没听懂，感觉没用，不做了
今天被好多没营养的题浪费时间了
骗我呢
任老师说这题挺好的
但我不会
看解析看了一个多小时，终于看明白了
没时间了，简单写思路
先推个DP
发现一行有 m 个数，单调增，共有 0~m m+1 种取值
说明每行只有一个数没有出现
设 f[i][j] 为第 i 行没有出现的数是 j 的方案数
不难发现 f[i][j]=f[i-1][0]+f[i-1][1]+...+f[i-1][j+1]
可以优化成 f[i][j]=f[i][j-1]+f[i-1][j+1]
把转移关系化成箭头，斜的不好看，“推开”成横平竖直的
答案可以转化为 平面上 从 (0, 0) 到 (n+m+1, n) 的路径数，其中路径不能碰到 y=x+1, y=x-m-2 两条直线（这里想了很久）
然后容斥
- 不考虑限制 从 (0, 0) 到 (x, y) 的路径数 为 \(x+y\choose x\) 代表一共要走 x+y 次，选 x 次 向右走
然后减去什么以A开头的和以B开头的
翻转之类的（这好像在这种不经过某直线路径数的时候很常见，卡特兰数一样）
具体看题解吧，反正我搞懂了，要回宿舍了没时间写了
C(n,m) 函数坑了我两次了
- 记得 n<m 的时候返回 0
- 记得 n<0 或 m<0 的时候返回 0
#include<iostream>
#include<cstring>
#include<algorithm>
#define mod 1000000007
using namespace std;
typedef long long ll;
const int N=5e6+100;
int n,m;
ll fact[N];
ll qpow(ll a,ll k,ll p) {
ll res=1;
while(k) {
if(k&1) res=res*a%p;
a=a*a%p,k>>=1;
}
return res;
}
ll C(ll n,ll m,ll p) {
if(n<0||m<0) return 0;
if(n<m) return 0;
return fact[n]*qpow(fact[m],mod-2,mod)%mod*qpow(fact[n-m],mod-2,mod)%mod;
}
void trans(ll &x,ll &y,ll a) {
swap(x,y);
x-=a,y+=a;
}
int main() {
scanf("%d%d",&n,&m);
fact[0]=1;
for(ll i=1;i<=3e6+100;i++) fact[i]=fact[i-1]*i%mod;
int ans=C(n+m+1+n,n,mod);
ll x=n+m+1,y=n;
while(x>=0&&y>=0) {
trans(x,y,1);
ans=((ans-C(x+y,x,mod))%mod+mod)%mod;
trans(x,y,-m-2);
ans=(ans+C(x+y,x,mod))%mod;
}
x=n+m+1,y=n;
while(x>=0&&y>=0) {
trans(x,y,-m-2);
ans=((ans-C(x+y,x,mod))%mod+mod)%mod;
trans(x,y,1);
ans=(ans+C(x+y,x,mod))%mod;
}
printf("%d\n",ans);
return 0;
}