例题整理
题1 1295. X的因子链
#include<iostream>
using namespace std;
const int N=110;
int n;
struct Node{
int p,s;
}f[N];
int C(int a,int b)
{
int res=1;
for(int i=1,j=a;i<=b;++i,--j)
res=res*j/i;
return res;
}
int main()
{
while(cin>>n)
{
int cnt=0,sum=0;
for(int i=2;i*i<=n;++i)
if(n%i==0)
{
int s=0;
while(n%i==0) n/=i,++s;
f[cnt++]={i,s},sum+=s;
}
if(n>1) f[cnt++]={n,1},sum++;
printf("%d ",sum);
int res=1;
for(int i=0;i<cnt;++i)
{
int s=f[i].s;
res*=C(sum,s);
sum-=s;
}
printf("%d\n",res);
}
return 0;
}
题2 1299. 五指山
#include<iostream>
using namespace std;
typedef long long LL;
LL n,d,x,y,a,b;
LL exgcd(LL a,LL b,LL& x,LL& y)
{
if(!b)
{
x=1,y=0;
return a;
}
LL d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%lld%lld",&n,&d,&x,&y);
//x+bd=y+an
LL gcd=exgcd(n,d,a,b);
if((y-x)%gcd) puts("Impossible");
else
{
b*=(y-x)/gcd;
n/=gcd;
printf("%lld\n",(b%n+n)%n);
}
}
return 0;
}
题3 1301. C 循环
#include<iostream>
using namespace std;
typedef long long LL;
LL a,b,c,k,z;
LL exgcd(LL a,LL b,LL& x,LL& y)
{
if(!b)
{
x=1,y=0;
return a;
}
LL d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main()
{
while(cin>>a>>b>>c>>k,a||b||c||k)
{
z=1ll<<k;//cx=b-a (mod 2^k)
LL x=0,y=0,d=exgcd(c,z,x,y);
if((b-a)%d) cout<<"FOREVER"<<endl;
else
{
x*=(b-a)/d;
cout<<(x%(z/d)+z/d)%(z/d)<<endl;
}
}
return 0;
}
题4 1223. 最大比例
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=110;
int n;
LL x[N],a[N],b[N];
LL gcd(LL a,LL b)
{
return b?gcd(b,a%b):a;
}
LL gcd_sub(LL a,LL b)
{
if(a<b) swap(a,b);
if(b==1) return a;
return gcd_sub(b,a/b);
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;++i)
scanf("%lld",&x[i]);
sort(x,x+n);
int cnt=0;
for(int i=1;i<n;++i)
if(x[i-1]!=x[i])
{
LL d=gcd(x[i],x[0]);
a[cnt]=x[i]/d,b[cnt]=x[0]/d,++cnt;
}
LL up=a[0],down=b[0];
for(int i=1;i<cnt;++i)
{
up=gcd_sub(up,a[i]);
down=gcd_sub(down,b[i]);
}
printf("%lld/%lld",up,down);
return 0;
}
题5 1225. 正则问题
#include<iostream>
using namespace std;
int k;
string str;
int dfs()
{
int res=0;
while(k<str.size())
{
if(str[k]=='(')//(...)
{
k++;//跳过(
res+=dfs();
k++;//跳过)
}
else if(str[k]=='|')//(...|..)
{
k++;//跳过|
res=max(res,dfs());
}
else if(str[k]==')') break;
else
{
k++;//跳过x
res++;
}
}
return res;
}
int main()
{
cin>>str;
cout<<dfs();
return 0;
}
题6 1296. 聪明的燕姿
#include<iostream>
#include<algorithm>
using namespace std;
const int N=50001;
int primes[N],cnt;
bool st[N];
int ans[N],len;
void init()
{
for(int i=2;i<N;++i)
{
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]*i<N;++j)
{
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
bool check(int x)
{
if(x<N) return !st[x];
for(int i=0;primes[i]<=x/primes[i];++i)
if(x%primes[i]==0) return false;
return true;
}
void dfs(int u,int pr,int s)//pr当前数,s要凑的约数之和
{
if(s==1)
{
ans[len++]=pr;
return;
}
if(s-1>(u<0?1:primes[u])&&check(s-1))
ans[len++]=pr*(s-1);//特判s=1+p
for(int i=u+1;primes[i]<=s/primes[i];++i)
{
int p=primes[i];
for(int j=p+1,t=p;j<=s;t*=p,j+=t)
if(s%j==0) dfs(i,pr*t,s/j);
}
}
int main()
{
init();
int s;
while(~scanf("%d",&s))
{
len=0;
dfs(-1,1,s);
printf("%d\n",len);
if(len)
{
sort(ans,ans+len);
for(int i=0;i<len;++i)
printf("%d ",ans[i]);
printf("\n");
}
}
return 0;
}