(T) 为测试数据组数，时限默认 (1s)
A. (Tle 10000,nle 10^8) ，求 ( ext{lcm}(1,2,dots,n)\% 2^{32}) ， (3s)
首先 (O(n)) 线性筛，处理出质数的前缀积，时间吃得消，但空间吃不消，所以把线性筛中那个bool数组改成bitset
然后 (O(log^2n)) 回答每个询问，枚举一个 (i) ，再二分出 (p^ile n) 且 (p^{i+1}>n) 的所有质数 (p) ，把答案乘上它们的积，用unsigned保存。
Code
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=100000003;
typedef unsigned int U;
int pr[6000003],tot;
U bit[(maxn>>5)+3],mul[6000003];
void set(int i){bit[i>>5]|=(1u<<(i&31));}
bool at(int i){return (bit[i>>5]>>(i&31))&1;}
void init(int n){
set(1);
mul[0]=1;
for(int i=2;i<=n;i++){
if(!at(i)){
pr[++tot]=i;
mul[tot]=mul[tot-1]*i;
}
for(int j=1;j<=tot&&i*pr[j]<=n;j++){
set(i*pr[j]);
if(i%pr[j]==0)break;
}
}
}
int main(){
init(100000000);
int T;
scanf("%d",&T);
for(int TT=1;TT<=T;TT++){
int n;
scanf("%d",&n);
U ANS=1;
for(int i=1;i<=27;i++){
int l=1,r=tot,mid,ans=0;
while(l<=r){
mid=(l+r)>>1;
if(pow(pr[mid],i)<=n)ans=mid,l=mid+1;
else r=mid-1;
}
ANS*=mul[ans];
}
printf("Case %d: %u
",TT,ANS);
}
return 0;
}
B. (Tle 2*10^5,nle 3*10^6) ，求 (sum_{i=1}^n sum_{j=i+1}^n ext{lcm}(i,j)\% 2^{64})
设 (f[n]=sum_{i=1}^{n-1} ext{lcm}(i,n)) 。
(f[n]=n*sum frac{i}{gcd(i,n)})
(f[n]=sum frac{n}{d}*frac{i}{d}*d)
(ecause frac{n}{d}) 与 (frac{i}{d}) 互质
( herefore f[n]=sum frac{2*φ(frac{n}{d})}{frac{n}{d}}*n)
(f[n]=sum_{i=1,j|n}^{n-1} frac{2*φ(j)}{j}*n)
Code
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long D;
const int maxn=3000003;
D ANS[maxn];
bool check[maxn];
int pr[300003],tot,phi[maxn];
void init(int n){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!check[i]){
pr[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot&&i*pr[j]<=n;j++){
check[i*pr[j]]=1;
if(i%pr[j]==0){
phi[i*pr[j]]=phi[i]*pr[j];
break;
}
else phi[i*pr[j]]=phi[i]*phi[pr[j]];
}
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j+=i){
ANS[j]+=D(i)*phi[i]/2*j;
}
ANS[i]+=ANS[i-1];
}
}
int main(){
init(3000000);
int T;
scanf("%d",&T);
for(int TT=1;TT<=T;TT++){
int n;
scanf("%d",&n);
printf("Case %d: %llu
",TT,ANS[n]);
}
return 0;
}
C. (Tle 325,a,ble 10^6,Lle 10^{12}) ，求最小的 (c) ，使得 ( ext{lcm}(a,b,c)=L)
首先求出 (x= ext{lcm}(a,b)) 。
然后请自行思考。简单题。
D. (Tle 2000,kle nle 10^6) ，求 (C(n,k)\% 1000003)
(C(n,k)=n!*k!^{-1}*(n-k)!^{-1})
水题。（由于 (C(n,k)) 不可能有因子 (1000003) ，所以不用lucas）
E. (T=10000,-10^8le all;numbersle 10^8) ，求方程 (Ax+By+C=0(x_1le xle x_2,y_1le yle y_2)) 的整数解个数。
exgcd+特判。
细节繁多，注意处理边界。
Code
#include<bits/stdc++.h>
#define f(x) ((-c-a*(x))/b)
using namespace std;
typedef long long D;
D gcd(D a,D b){return b==0?a:gcd(b,a%b);}
D egcd(D a,D b,D& x,D& y){
if(b==0){
x=1;
y=0;
return a;
}
D ans=egcd(b,a%b,x,y);
D tmp=x;
x=y;
y=tmp-a/b*y;
return ans;
}
D cal(D a,D b,D c){
D x,y;
D g=egcd(a,b,x,y);
if(c%g!=0)return -1;
x*=c/g;
b=abs(b);
D ans=x%b;
if(ans<=0)ans+=b;
return ans;
}
signed main(){
int T;
scanf("%d",&T);
for(int TT=1;TT<=T;TT++){
D a,b,g,c,xl,xr,yl,yr,x,y,ans=0;
double f1,f2;
scanf("%lld%lld%lld%lld%lld%lld%lld",&a,&b,&c,&xl,&xr,&yl,&yr);
if(a==0||b==0){
if(a==0){
if(b==0){
if(c)ans=0;
else ans=(D)(xr-xl+1)*(yr-yl+1);
}
else{
if(c%b==0&&-c/b>=yl&&-c/b<=yr)ans=xr-xl+1;
else ans=0;
}
}
else if(b==0){
if(c%a==0&&-c/a>=xl&&-c/a<=xr)ans=yr-yl+1;
else ans=0;
}
}
else{
x=cal(a,b,-c);
y=f(x);
g=gcd(a,b);
if(x!=-1){
D x_l,x_r,y_l,y_r;
if((D)g*b<0){
x_l=ceil(double(xr-x)*g/b);
x_r=floor(double(xl-x)*g/b);
}
else{
x_l=ceil(double(xl-x)*g/b);
x_r=floor(double(xr-x)*g/b);
}
if((D)g*a<0){
y_l=ceil(double(y-yl)*g/a);
y_r=floor(double(y-yr)*g/a);
}
else{
y_l=ceil(double(y-yr)*g/a);
y_r=floor(double(y-yl)*g/a);
}
D l=max(x_l,y_l),r=min(x_r,y_r);
if(l<=r)ans=r-l+1;
}
}
printf("Case %d: %lld
",TT,ans);
}
return 0;
}
F. (Tle 300,x,nle 10^6) ，求 (sum_{a=1}^n sum_{b=1}^n gcd(x^a-1,x^b-1))
首先 (gcd(x^a-1,x^b-1)=x^{gcd(a,b)}-1) 。
证明：见这篇博客
经过推算可得， (gcd(i,n)=m) 的 (i) 的个数 (=φ(n/m))
对于每个 (m) ， (gcd(i,j)=m) 的 ((i,j)) 的个数是 ((sum_{k=1}^{n/m} φ(k))*2-1) 。
因此我们可以除法分块，每一个块内 (n/m) 相等，那么每一个块 ([l,r]) 的答案就是 ((sum_{i=l}^r (x^i-1))*((sum_{k=1}^{n/m} φ(k))*2-1)) 。
Code
#include<cstdio>
using namespace std;
const int maxn=1000003,mod=1000000007;
int phi[maxn],pr[100003],tot,sum[maxn];
bool check[maxn];
int Plus(int x,int y){return (x+=y)>=mod?x-mod:x;}
int Minus(int x,int y){return (x+=mod-y)>=mod?x-mod:x;}
int mul(long long x,int y){return x*y%mod;}
int qpow(int x,int y){
int ans=1;
while(y){
if(y&1)ans=mul(ans,x);
x=mul(x,x);
y>>=1;
}
return ans;
}
int Div(int x,int y){return mul(x,qpow(y,mod-2));}
void init(int n){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!check[i]){
pr[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot&&i*pr[j]<=n;j++){
check[i*pr[j]]=1;
if(i%pr[j]==0){
phi[i*pr[j]]=phi[i]*pr[j];
break;
}
else phi[i*pr[j]]=phi[i]*phi[pr[j]];
}
}
for(int i=1;i<=n;i++)sum[i]=Plus(sum[i-1],phi[i]);
}
int get_sum_from_x_l_to_x_r(int x,int l,int r){
return x==1?r-l+1:Div(mul(qpow(x,l),Minus(qpow(x,r-l+1),1)),Minus(x,1));
}
int calc(int x,int n,int i,int j){
return mul(Minus(get_sum_from_x_l_to_x_r(x,i,j),j-i+1),Minus(mul(sum[n/i],2),1));
}
int main(){
init(1000000);
int T;
scanf("%d",&T);
while(T--){
int x,n,ans=0;
scanf("%d%d",&x,&n);
for(int i=1,j;i<=n;i=j+1){
j=n/(n/i);
ans=Plus(ans,calc(x,n,i,j));
}
printf("%d
",ans);
}
return 0;
}
其他题目
LOJ 6392 密码学第三次小作业
解
(ecause gcd(e_1,e_2)=1)
( herefore e_1x+e_2y=1)
( herefore m^{e_1x+e_2y}=m=c_1^xc_2^y)
所以只需要快速幂。如果 (x<0||y<0) 就计算逆元。
Codeforces 487C
题意
询问是否存在 (1) 到 (n) 的排列 (P) ，使得对于每个 (1le ile n) ， ((prod_{j=1}^i P_j) mod n) 互不相同。如果存在则构造一组方案。
解
首先第一个数是 (1) ，第 (n) 个数是 (n) 。
然后如果 (n>4) 且 (n) 是合数就不可能。原因： (n>4) 且 (n) 是合数时，((n-1)!≡0(\% n))
如果 (n>4) 且 (n) 是质数，那么构造 (a[i]=i/(i-1)mod n) 。
证明：假设存在 (a_i≡a_j(\% n)) 。
那么 (i/(i-1)≡j/(j-1)(\% n)) 。
(1+frac{1}{i-1}≡1+frac{1}{j-1}(\% n)) 。
(i≡j(\% n))
矛盾。所以这种构造方案是正确的。
NOI2018 屠龙勇士
解
选剑的话用multiset维护。
然后列方程：设选的剑攻击力为 (t_i) ，那么 (a_i≡x_i*t_i(\% p_i)) ，用exgcd解出，作为一个方程放到方程组 (x≡x_i(\% p_i)) 里用excrt解出。
然后由于每条龙血量必须攻击到 (le 0) 。
Code
#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
typedef long long D;
const int maxn=200003;
D g;
D egcd(D a,D b,D &x,D &y){
if(b==0){
x=1;
y=0;
return a;
}
D ans=egcd(b,a%b,x,y);
D tmp=x;
x=y;
y=tmp-a/b*y;
return ans;
}
D cal(D a,D b,D c){
D x,y;
g=egcd(a,b,x,y);
if(c%g!=0)return -1;
b=abs(b/g);
x=(x*__int128(c/g)%b+b)%b;
return x;
}
D calc(D a,D b,D m){ // ax===b(%m)
return cal(a,m,b);
}
D excrt(int n,D a[],D m[]){
D x=a[1],l=m[1];
for(int i=2;i<=n;i++){
D t=calc(l,(m[i]+a[i]-x%m[i])%m[i],m[i]);
if(t==-1)return -1;
x=(x+__int128(t)*l)%(l*(m[i]/g));
l*=m[i]/g;
}
return x;
}
int n,m;
D a[maxn],p[maxn],t[maxn],A[maxn],M[maxn],mx;
multiset<D> st;
multiset<D>::iterator it;
int main(){
int T;
scanf("%d",&T);
while(T--){
st.clear();
mx=0;
bool flag=1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",a+i);
for(int i=1;i<=n;i++)scanf("%lld",p+i);
for(int i=1;i<=n;i++)scanf("%lld",t+i);
for(int i=1;i<=m;i++){
D x;
scanf("%lld",&x);
st.insert(x);
}
for(int i=1;i<=n;i++){
it=st.upper_bound(a[i]);
if(it!=st.begin())it--;
D s=*it;
A[i]=cal(s,p[i],a[i]);
if(A[i]==-1){flag=0;break;}
M[i]=p[i]/g;
mx=max(mx,(a[i]+s-1)/s);
st.erase(it);
st.insert(t[i]);
}
if(!flag)puts("-1");
else{
D ans=excrt(n,A,M);
if(ans==-1)puts("-1");
else{
ans+=max(0ll,(mx-ans+M[n]-1)/M[n]);
printf("%lld
",ans);
}
}
}
return 0;
}