Pairs of integers
题意：给出一个整数N（N<=1e9）求两个整数X,Y使得X+Y=N，求所有的解
其中Y是X直接去掉一位后得到的（1034->134,100->00.etc）
题解：对于整数X，我们枚举它的每一位（第i位），并且枚举这一位上所有可能的数字d
令第i位前的数字构成的数为x，第i位后的数字构成的数为y
那么就有(x*10^i+d*10^{i-1}+y+x*10^{i-1}+y=N)
因此(11*10^{i-1}+2y=N-d*10^{i-1})
解不定方程即可，然后搞出所有解就行了
用map实现本题十分方便（既可以去重也可以排序）
P.S.
- 本题的输出十分有意思
- 我觉得可以不用代码里的倍增吧，得到最小的非负整数解很容易啊
code：
#include<cstdio>
#include<map>
using namespace std;
typedef long long ll;
ll N,P10[15];
map<ll,ll>ans;
void exgcd(ll a,ll b,ll &g,ll &x,ll &y)
{
if(!b){x=1;y=0;g=a;return;}
exgcd(b,a%b,g,x,y);
ll xx=x;
x=y;y=xx-a/b*y;
}
inline int ws(ll x)
{
if(!x)return 1;
int anss=0;
for(;P10[anss]<=x;++anss);
return anss;
}
int main()
{
P10[0]=1;
for(int i=1;i<=10;++i)P10[i]=P10[i-1]*10ll;
while(scanf("%lld",&N)!=EOF)
{
ans.clear();
int len=ws(N);
if(N%P10[len-1]==0)ans[N]=0;
for(int i=1;i<=len;++i)
{
ll a=11*P10[i-1],b=2,g=0,x=0,y=0;
exgcd(a,b,g,x,y);
ll xx=x,yy=y;
for(int d=0;d<10;++d)
{
x=xx,y=yy;
ll c=N-1ll*d*P10[i-1];
if(c%g)continue;
ll s=c/g,_a=0,_b=0;
x*=s,y*=s;_a=a/g,_b=b/g;
y=(y%_a+_a)%_a;
for(;y<P10[i-1];y+=_a)
{
x=(c-y*b)/a;
ll X=x*P10[i]+d*P10[i-1]+y,Y=x*P10[i-1]+y;
if(X!=Y&&X>=0&&Y>=0)ans[X]=Y;
}
}
}
printf("%lld
",ans.size());
for(map<ll,ll>::iterator it=ans.begin();it!=ans.end();it++)
printf("%lld + %0*lld = %lld
",it->first,ws(it->first)-1,it->second,N);
}
return 0;
}
最小公倍数的最小和
注意细节：
1.n=1
2.n为素数
3.n=2^31-1（答案会越界）
#include<bits/stdc++.h>
using namespace std;
int n,kase;
int main()
{
while(scanf("%d",&n)==1&&n)
{
long long ans=0;int nn=n,mx=(int)sqrt(n);
for(int i=2;i<=mx;++i)
{
int cnt=1;
while(n%i==0)n/=i,cnt*=i;
if(cnt!=1)ans+=1ll*cnt;
if(n==1)break;
}
if(ans==0)ans=1ll*nn+1;
else if(n!=1)ans+=1ll*n;
if(ans==1ll*nn)++ans;
if(nn==1)ans=2;
printf("Case %d: %lld
",++kase,ans);
}
return 0;
}
选择与除法
质因数分解。统计指数就可以了
#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int pr[N],p,q,r,s;
double ans;
inline int cp(int &x,int d)
{
int cnt=0;
while(x%d==0)x/=d,++cnt;
return cnt;
}
inline void work(int x,int d)
{
int mx=(int)sqrt(x+1);
for(int i=2;i<=mx&&x!=1;++i)
if(x%i==0)pr[i]+=d*cp(x,i);
if(x>1)pr[x]+=d;
}
inline void ad(int x,int d)
{
for(int i=2;i<=x;++i)
work(i,d);
}
inline void solve()
{
ans=1;
for(int i=2;i<=N-5;++i)
ans*=pow(i,pr[i]),pr[i]=0;
printf("%.5lf
",ans);
}
int main()
{
while(scanf("%d%d%d%d",&p,&q,&r,&s)==4)
{
ad(p,1);ad(q,-1);
ad(s,1);ad(r,-1);
ad(r-s,1);ad(p-q,-1);
solve();
}
return 0;
}
交表
题意：求出整数对个数(x,y)(x,y<=n n<=5e4)使得其最大公约数为1
题解：这样的整数对除(1,1)其他的x不等于y
不妨设x>y(x<y同理)那么只要确定x，答案就是phi(x)
筛出所有phi(x)，求出前缀和即可
code:
#include<bits/stdc++.h>
using namespace std;
const int N=50005;
vector<int>pr;
int phi[N],sm[N],n;
bool flag[N];
inline void pre()
{
int m=N-5;
for(int i=2;i<=m;++i)
{
if(!flag[i]){phi[i]=i-1;pr.push_back(i);}
for(int j=0;j<pr.size();++j)
{
if(i*pr[j]>m)break;
flag[i*pr[j]]=true;
if(i%pr[j])phi[i*pr[j]]=phi[i]*phi[pr[j]];
else{phi[i*pr[j]]=phi[i]*pr[j];break;}
}
}
for(int i=2;i<=m;++i)
sm[i]=sm[i-1]+phi[i];
}
int main()
{
pre();
while(scanf("%d",&n)==1&&n)
printf("%d
",sm[n]*2+1);
return 0;
}
树林里的树
题解：
可以发现坐标轴上有且仅有4个点可以看到，单独考虑
发现只用考虑右上角的点就行了（其他方位同理）
由于列数较少行数较多，因此枚举列数
对于列x，能看到的当且仅当其纵坐标与x互质
不难想到欧拉函数
稍稍扩展可以证明(kx+1到(k+1)x)（其中k为正整数）中与x互质的数的个数仍然为phi(x)
简略证明：
若d（d<x）与x互质，那么d+x仍然与x互质
若e(e<=x)与x不互质，那么e+x仍然与x不互质
由此可以快速计算每列可以看到多少树
至于余数部分，暴力计算统计即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2005;
vector<int>p;
int lp[N],phi[N],a,b;
bool flag[N];
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
inline void pre()
{
int m=N-5;phi[1]=1;
for(int i=2;i<=m;++i)
{
if(!flag[i]){phi[i]=i-1;p.push_back(i);}
for(int j=0;j<p.size();++j)
{
if(i*p[j]>m)break;
flag[i*p[j]]=true;
if(i%p[j])phi[i*p[j]]=phi[i]*phi[p[j]];
else{phi[i*p[j]]=phi[i]*p[j];break;}
}
}
}
int main()
{
pre();
while(scanf("%d%d",&a,&b)==2&&a&&b)
{
ll ans=0,t=0;
for(int i=1;i<=a;++i)
{
int d=b/i;
ans+=1ll*d*phi[i];
for(int j=d*i+1;j<=b;++j)
if(gcd(j,i)==1)++ans;
}
ans*=4;ans+=4;t=1ll*(a*2+1)*(b*2+1)-1;
printf("%.10lf
",(double)ans/t);
}
return 0;
}
数论难题
题解：
由题意可以知道枚举每个模数的余数，然后直接上中国剩余定理即可
但是倘若总的可能情况过大，这样可能超时
可以这样解决：
首先找到一个i使得(K_i/X_i)（(K_i)，(X_i)如题目所述）尽量小
至于为何如此选择，我认为原因有二：
- 让可能的解分布尽可能稀疏，减少判断次数
- 对于剩下来的其他条件，由于最难满足的已经被剔除(就是之前选出来的)，可能解更有可能成为真正的解
以这个基数为基础，暴力枚举判断其他模数下是否满足条件输出即可
因为总的可能情况很大，因此这样做复杂度可以保证
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef set<long long>::iterator si;
ll C,S,BASE,X[15],K[15];
set<ll>Y[15];
inline ll read(){ll x;scanf("%lld",&x);return x;}
inline ll pre()
{
ll M=1;BASE=0;
for(ll i=1;i<=C;++i)
{
scanf("%lld%lld",&X[i],&K[i]);
M*=K[i];Y[i].clear();
for(ll j=1;j<=K[i];++j)
Y[i].insert(read());
if(!BASE||K[BASE]*X[i]>K[i]*X[BASE])BASE=i;
}
return M;
}
vector<ll>Ans;
ll a[15];
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b){x=1,y=0;return;}
exgcd(b,a%b,y,x);y-=a/b*x;
}
inline ll china()
{
ll M=1,ans=0;
for(ll i=1;i<=C;++i)M*=X[i];
for(ll i=1;i<=C;++i)
{
ll w=M/X[i],x=0,y=0;
exgcd(X[i],w,x,y);
ans=(ans+w*y%M*a[i]%M)%M;
}
return (ans+M)%M;
}
void dfs(ll p)
{
if(p==C+1){Ans.push_back(china());return;}
for(si it=Y[p].begin();it!=Y[p].end();it++)
a[p]=*it,dfs(p+1);
}
inline void work1()
{
Ans.clear();
dfs(1);
ll M=1;
for(ll i=1;i<=C;++i)M*=X[i];
sort(Ans.begin(),Ans.end());
for(ll i=0;S;++i)
for(size_t j=0;j<Ans.size();++j)
{
ll x=i*M+Ans[j];
if(x<=0)continue;
printf("%lld
",x);
if(--S==0)break;
}
}
inline void work2()
{
for(ll i=0;S;++i)
for(si it=Y[BASE].begin();it!=Y[BASE].end();it++)
{
ll x=i*X[BASE]+*it;
if(x<=0)continue;
bool flag=false;
for(ll k=1;k<=C;++k)
{
if(k==BASE)continue;
if(!Y[k].count(x%X[k]))
{
flag=true;break;
}
}
if(flag)continue;
printf("%lld
",x);
if(--S==0)break;
}
}
int main()
{
while(scanf("%lld%lld",&C,&S)==2&&C&&S)
pre()<=10000ll?work1():work2(),puts("");
return 0;
}
帮帮Tomisu
题意：(2-N!)中有多少个数满足它们的所有质因子都大于(M)其中(N>=M)
题解：考察phi(M!)表示小于M!中与M!互质的数的个数
这些数一定满足它们的所有质因子都大于M（否则就和M!不互质了）
根据树林里的树这道题，那么最终的答案就是N!/M!*phi(M!)
那么如何求(phi(M!))呢？
考虑递推。假设我们已求得(phi(i!))要求(phi((i+1)!))
由欧拉函数通式
(varphi)((x)=xprod_{i=1}^n(1-frac{1}{p_i}))
其中(p_1), (p_2)……(p_n)为(x)的所有质因数，(x)是不为(0)的整数
因此如果i+1为素数，则(phi((i+1)!)=(i+1)*phi(i!)/(i+1)*i)
如果i+1不是素数，则(phi((i+1)!)=(i+1)*phi(i!))(因为i+1的所有质因数都被包含在i!中)
#include<bits/stdc++.h>
using namespace std;
const int mod=100000007,M=1e7+5;
int n,m,fac[M];
vector<int>p;
bitset<M>flag;
inline void pre()
{
int m=M-5;
for(int i=2;i<=m;++i)
{
if(!flag[i])p.push_back(i);
for(size_t j=0;j<p.size();++j)
{
int num=p[j]*i;
if(num>m)break;
flag[num]=true;
if(i%p[j]==0)break;
}
}
fac[1]=1;
for(int i=2;i<=m;++i)
fac[i]=1ll*fac[i-1]*(flag[i]?i:i-1)%mod;
}
int main()
{
pre();
while(scanf("%d%d",&n,&m)==2&&n&&m)
{
int ans=fac[m];
for(int i=m+1;i<=n;++i)
ans=1ll*ans*i%mod;
printf("%d
",ans-1);
}
return 0;
}
约瑟夫的数论问题/余数求和
题解：
(sum_{i=1}^{n} k mod i)
(=sum_{i=1}^{n}(k- lfloorfrac{k}{i}
floor *i))
(=k*n-sum_{i=1}^{n}lfloorfrac{k}{i}
floor *i)
后面那一部分可以用整除分块计算
注意细节
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
int n,k;
ll ans;
int main()
{
scanf("%d%d",&n,&k);
ans=1ll*n*k;
for(ll l=1,r;l<=k&&l<=n;l=r+1)
{
r=min(k/(k/l),1ll*n);
ans-=(l+r)*(r-l+1)/2*(k/l);
}
cout<<ans;
return 0;
}
(LOJ10038 A Horrible Poem，POI2012)[https://loj.ac/problem/10038]
题意：给出一个长度为n的字符串S（n<=5e5）,接下来有q（q<=2e6）个询问
每个询问输入两个数a，b，求S[a,b]内最短循环节长度（每个循环节都是完整的）
题解：
本题十分有趣~~
考虑对于每一个询问，枚举最短循环节长度进行判断
根据套路，可以先用哈希进行预处理，然后比较border（这样可以做到O(1)判断）
inline bool judge(int l,int r,int len){return get_hash(l,r-len)==get_hash(l+len,r);}
//判断l到r的区间中长度为len的循环节是否存在
而后容易想到循环节长度一定是区间长度的约数
枚举约数判断
但是这样仍然不行
如何优化呢？
不妨假设最短循环节长度为len，循环了k次
对于任意(d|k,len imes d)也一定是循环节长度
因此只要(k!=1)我们总是能找到一个素数p满足p|k
此时(len imes k/p)是循环节长度，不断迭代即可
意即我们不用枚举所有约数，枚举素因子足矣
但这样就要求快速获得一个数的质因数分解
上线性筛就可以了
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,mod=91203991;
char ch[N];
int n,base=31,p[N],hash[N],lp[N];
bool flag[N];
vector<int>pm;
inline int read()
{
int s=0,w=1; char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
for(;isdigit(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
return s*w;
}
inline void pre1()
{
p[0]=1;hash[0]=1;
for(int i=1;i<=n;++i)
{
p[i]=1ll*p[i-1]*base%mod;
hash[i]=(1ll*hash[i-1]*base%mod+ch[i]-'a'+1)%mod;
}
}
inline void pre2()
{
lp[1]=1;
for(int i=2;i<=n;++i)
{
if(!flag[i]){lp[i]=i;pm.push_back(i);}
for(size_t j=0;j<pm.size();++j)
{
int num=pm[j]*i;
if(num>n)break;
lp[num]=pm[j];flag[num]=true;
if(i%pm[j]==0)break;
}
}
}
inline int get_hash(int l,int r){return ((hash[r]-1ll*hash[l-1]*p[r-l+1]%mod)%mod+mod)%mod;}
inline bool judge(int l,int r,int len){return get_hash(l,r-len)==get_hash(l+len,r);}
inline int get_ans(int l,int r)
{
int len=r-l+1;
if(judge(l,r,1))return 1;
vector<int>fac;
while(len>1)
{
fac.push_back(lp[len]);
len/=lp[len];
}
len=r-l+1;
for(size_t i=0;i<fac.size();++i)
if(judge(l,r,len/fac[i]))len/=fac[i];
return len;
}
int main()
{
n=read();
scanf("%s",ch+1);
pre1();pre2();
int q=read();
while(q--)
{
int l=read(),r=read();
printf("%d
",get_ans(l,r));
}
return 0;
}