头像

JimmyFlower




离线:5个月前


活动打卡代码 AcWing 203. 同余方程

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;
}


活动打卡代码 AcWing 202. 最幸运的数字

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;
}


活动打卡代码 AcWing 201. 可见的点

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;
}


活动打卡代码 AcWing 200. Hankson的趣味题

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;
}


活动打卡代码 AcWing 199. 余数之和

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;
}


活动打卡代码 AcWing 198. 反素数

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;
}


活动打卡代码 AcWing 197. 阶乘分解

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;
}


活动打卡代码 AcWing 196. 质数距离

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;
        if(tot<2){printf("There are no adjacent primes.\n");continue;}
        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;
}


活动打卡代码 AcWing 323. 战略游戏

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];
inline void add(int x,int y)
{
    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);
                add(x,y),add(y,x);
            }
        }
        memset(f,0x3f,sizeof(f));
        treedp(root,n);
        printf("%d\n",min(f[root][0],f[root][1]));  
    }
    return 0;
}


活动打卡代码 AcWing 320. 能量项链

JimmyFlower
6个月前
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ri register int
using namespace std;
const int N=110;
int n,ans=0,f[2*N][2*N],head[2*N],tail[2*N];
int main()
{
    scanf("%d",&n);
    for(ri i=1;i<=n;i++) scanf("%d",&head[i]),head[n+i]=head[i];
    tail[n]=tail[2*n]=head[1];
    for(ri i=1;i<=n-1;i++) tail[i]=tail[n+i]=head[i+1];
    memset(f,0,sizeof(f));
    for(ri i=2;i<=n;i++)
        for(ri l=1,r=i;r<=2*n;l++,r++)
            for(ri k=l;k<=r-1;k++)
                f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+head[l]*tail[k]*tail[r]);
    for(ri l=1,r=n;r<=2*n;l++,r++) ans=max(ans,f[l][r]);
    printf("%d",ans);
    return 0;
}