JimmyFlower

2894

JimmyFlower
5个月前
#include<cstdio>
using namespace std;
typedef long long ll;
ll a,b,k,d,x,y;
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(!a) d=b,x=0,y=1;
else exgcd(b%a,a,d,y,x),x-=b/a*y;
}
int main()
{
scanf("%lld %lld",&a,&b);
exgcd(a,b,d,x,y);
printf("%lld",(x%b+b)%b);
return 0;
}


JimmyFlower
5个月前
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ri register int
using namespace std;
typedef long long ll;
ll L,d,p,t,ans,cnt=0;
ll gcd(ll a,ll b){return !a?b:gcd(b%a,a);}
ll mul(ll a,ll b,ll c)
{
ll res=0;
while(b)
{
if(b&1) res=(res+a)%c;
a=(a<<1)%c,b>>=1;
}
return res;
}
ll pow_(ll a,ll b,ll c)
{
ll res=1%c;
while(b)
{
if(b&1) res=mul(res,a,c);
a=mul(a,a,c),b>>=1;
}
return res;
}
ll phi(ll n)
{
ll t=sqrt(n+1),res=n;
for(ri i=2;i<=t;i++)
if(n%i==0)
{
res=res/i*(i-1);
while(n%i==0) n/=i;
}
if(n>1) res=res/n*(n-1);
return res;
}
int main()
{
while(scanf("%lld",&L)&&L)
{
d=gcd(L,8),p=phi(9LL*L/d);
if(gcd(10,9LL*L/d)!=1LL){printf("Case %lld: %lld\n",++cnt,0);continue;}
t=sqrt(p+1),ans=p;
for(ll i=1;i<=t;i++)
{
if(p%i==0&&pow_(10,i,9LL*L/d)==1LL) ans=min(ans,i);
if(p%i==0&&pow_(10,p/i,9LL*L/d)==1LL) ans=min(ans,p/i);
}
printf("Case %lld: %lld\n",++cnt,ans);
}
return 0;
}


JimmyFlower
6个月前
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ri register int
using namespace std;
const int N=1010;
bool isp[N];
int T,n,cnt=0,ans=0,tot,p[N],e[N];
void euler(int n)
{
tot=0;
memset(isp,true,sizeof(isp)); memset(e,0,sizeof(e));
isp[1]=false,e[1]=1;
for(ri i=2;i<=n;i++)
{
if(isp[i]) p[++tot]=i,e[i]=i-1;
for(ri j=1;j<=tot&&i*p[j]<=n;j++)
{
isp[i*p[j]]=false;
if(i%p[j]==0){e[i*p[j]]=e[i]*p[j];break;}
else e[i*p[j]]=e[i]*e[p[j]];
}
}
}
int main()
{
euler(1000);
scanf("%d",&T);
while(T--)
{
ans=0;
scanf("%d",&n); cnt++;
for(ri i=2;i<=n;i++) ans+=e[i];
printf("%d %d %d\n",cnt,n,2*ans+3);
}
return 0;
}


JimmyFlower
6个月前
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ri register int
using namespace std;
const int N=45010;
bool d_is_prime,isp[N];
int tot=0,p[N];
int n,a,b,c,d,ma,mb,mc,md,ans;
void make_prime(int x)
{
memset(isp,true,sizeof(isp)); isp[0]=isp[1]=false;
for(ri i=2;i<=x;i++)
{
if(isp[i]) p[++tot]=i;
for(ri j=1;j<=tot&&i*p[j]<=x;j++)
{
isp[i*p[j]]=false;
if(i%p[j]==0) break;
}
}
}
void solve(int pri)
{
ma=mb=mc=md=0;
while(a%pri==0) a/=pri,ma++;
while(b%pri==0) b/=pri,mb++;
while(c%pri==0) c/=pri,mc++;
while(d%pri==0) d/=pri,md++;
if(!md) return;
if(ma>mc&&mb<md&&mc==md) ans*=1;
else if(ma>mc&&mb==md&&mc<=md) ans*=1;
else if(ma==mc&&mb<md&&mc<=md) ans*=1;
else if(ma==mc&&mb==md&&mc<=md) ans=ans*(md-mc+1);
else ans=0;
}
int main()
{
make_prime(45000);
scanf("%d",&n);
for(ri i=1;i<=n;i++)
{
ans=1;
scanf("%d %d %d %d",&a,&c,&b,&d);
for(ri i=1;i<=tot&&p[i]<=d;i++) solve(p[i]);
if(d>1) solve(d);
printf("%d\n",ans);
}
return 0;
}


JimmyFlower
6个月前
#include<cmath>
#include<cstdio>
#include<algorithm>
#define ri register int
typedef long long ll;
using namespace std;
ll n,k,ans;
int main()
{
scanf("%lld %lld",&n,&k); ans=n*k;
for(ll l=1,r;l<=n;l=r+1)
{
if(k/l==0) break;
r=min(k/(k/l),n);
ans-=(k/l)*(l+r)*(r-l+1)/2;
}
printf("%lld",ans);
return 0;
}


JimmyFlower
6个月前
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ri register int
using namespace std;
typedef long long ll;
ll n,ans=0,maxi=0;
ll prime[11]={0,2,3,5,7,11,13,17,19,23,29};
void dfs(ll x,ll res,ll ind,ll last)
{
if(res>n) return;
if(ind>maxi||(ind==maxi&&res<ans)) ans=res,maxi=ind;
if(x>10) return;
for(ll i=0,t=1;i<=last;i++,t*=prime[x])
{
if(res*t>n) break;
dfs(x+1,res*t,ind*(i+1),i);
}
}
int main()
{
scanf("%lld",&n);
dfs(1,1,1,30);
printf("%lld",ans);
return 0;
}


JimmyFlower
6个月前
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ri register int
using namespace std;
typedef long long ll;
const int N=1000010;
bool isp[N];
ll n,res,tot=0,p[N];
void make_prime(int n)
{
memset(isp,true,sizeof(isp)); isp[0]=isp[1]=false;
for(ri i=2;i<=n;i++)
{
if(isp[i]) p[++tot]=i;
for(ri j=1;j<=tot&&i*p[j]<=n;j++)
{
isp[i*p[j]]=false;
if(i%p[j]==0) break;
}
}
}
int main()
{
scanf("%d",&n);
make_prime(n);
for(ri i=1;i<=tot;i++)
{
res=0;
for(ll j=p[i];j<=n;j*=p[i]) res+=n/j;
if(res) printf("%d %d\n",p[i],res);
}
return 0;
}


JimmyFlower
6个月前
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
#define ri register int
using namespace std;
typedef long long ll;
const int N=1000010,M=50010;
bool v[N],isp[N];
int os,cnt,tot,p[N],ans_min[3],ans_max[3];
ll l,r;
void make_prime(int n)
{
tot=0;
memset(isp,true,sizeof(isp)); isp[0]=isp[1]=false;
for(ri i=2;i<=n;i++)
{
if(isp[i]) p[++tot]=i;
for(ri j=1;j<=tot&&i*p[j]<=n;j++)
{
isp[i*p[j]]=false;
if(i%p[j]==0) break;
}
}
}
signed main()
{
while(scanf("%lld %lld",&l,&r)!=EOF)
{
os=l;
make_prime(M);
memset(v,true,sizeof(v));
for(ri i=1;i<=tot;i++)
for(ll j=max(2LL*p[i],(l-1)/p[i]*p[i]+p[i]);j<=r;j+=p[i])
v[j-os]=false;
tot=0;
for(ri i=l-os;i<=r-os;i++)
if(v[i]&&i+os>1) p[++tot]=i+os;
ans_min[1]=ans_max[1]=p[1],ans_min[2]=ans_max[2]=p[2];
for(ri i=3;i<=tot;i++)
{
if(p[i]-p[i-1]<ans_min[2]-ans_min[1]) ans_min[1]=p[i-1],ans_min[2]=p[i];
if(p[i]-p[i-1]>ans_max[2]-ans_max[1]) ans_max[1]=p[i-1],ans_max[2]=p[i];
}
printf("%d,%d are closest, %d,%d are most distant.\n",ans_min[1],ans_min[2],ans_max[1],ans_max[2]);
}
return 0;
}


JimmyFlower
6个月前
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ri register int
using namespace std;
const int root=0;
int len=0,last[2000];
int n,x,y,k,f[2000][3];
struct edge{int x,y,next;}a[3010];
{
len++;
a[len].x=x,a[len].y=y;
a[len].next=last[x],last[x]=len;
}
void treedp(int x,int fa)
{
f[x][0]=0,f[x][1]=1;
for(ri i=last[x];i;i=a[i].next)
{
int y=a[i].y;
if(y==fa) continue;
treedp(y,x);
f[x][0]+=f[y][1];
f[x][1]+=min(f[y][0],f[y][1]);
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(last,0,sizeof(last)); len=0;
for(ri i=1;i<=n;i++)
{
scanf("%d:(%d)",&x,&k);
for(ri j=1;j<=k;j++)
{
scanf("%d",&y);
}
}
memset(f,0x3f,sizeof(f));
treedp(root,n);
printf("%d\n",min(f[root][0],f[root][1]));
}
return 0;
}


JimmyFlower
6个月前
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ri register int
using namespace std;
const int N=110;
int main()
{
scanf("%d",&n);