头像

LittleMonk


访客:404

在线 


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

#pragma GCC optimize(3)
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;

typedef long long ll;

const int maxn=1e6+10;
int primes[maxn],cnt;
bool vis[maxn];
ll sum;


//线性筛打表[2,sqrt(n)]
void get(int n)
{
    cnt=0;
    memset(vis,false,sizeof(vis));
    for(int i=2;i<=n;i++){
        if(!vis[i])primes[cnt++]=i;
        for(int j=0;i*primes[j]<=n/i;j++){
            vis[i*primes[j]]=true;
            if(i%primes[j]==0)break;
        }
    }
}

//区间筛
void get(int l,int r)
{
    memset(vis,false,sizeof(vis));//一定要清零
    for(int i=0;i<cnt;i++){
        ll p=primes[i];
        for(ll j=max(p+p,(l+p-1)/p*p);j<=r;j+=p){//之所以取max是为了节省时间取到区间l到r内出现的第一个p的倍数
            vis[j-l]=true;//之所以要减去l是为了防止数组下标溢出
        }
    }
    cnt=0;
    for(int i=0;i<=r-l;i++){
        if(!vis[i]&&i+l>=2)primes[cnt++]=i+l;//把区间l到r内筛完以后得到的素数赋到数组primes中去,且要防止边界情况l<2
    }
    for(int i=0;i<cnt;i++)sum+=primes[i];
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int a,b;
    while(cin>>a>>b){
        get(50010);
        sum=0;
        get(a,b);
        cout<<sum<<endl;
    }
    return 0;
}



题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1852

tle:

错误的代码:

#pragma GCC optimize("O3")
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long ll;

ll quick_pow(int x,int y,int mod)
{
    ll ans=1;
    while(y){
        if(y&1)ans=(ans*x)%mod;
        x=(x*x)%mod;
        y>>=1;
    }
    return ans%mod;
}

ll quick_mul(int x,int y,int mod)
{
    ll ans=0;
    while(y){
        if(y&1)ans=(ans+x)%mod;
        x=(x+x)%mod;
        y>>=1;
    }
    return ans%mod;
}

int main()
{
    int n,k;
    while(~scanf("%d%d",&n,&k)&&n){
        k=k*250;//乘法逆元
        ll a=(quick_pow(2,3*n+1,k)-1)%k;
        ll b=((quick_pow(251,n+1,k)-1)%k/250)%k;
        ll m=quick_mul(a,b,k)%k;
        //ll m=a*b%k;
        k/=250;
        printf("%lld\n",quick_pow(2008,m,k)%k);
    }
    return 0;
}

直接乘tle,快速乘也tle




题目链接 :https://www.acwing.com/problem/content/224/

青蛙的约会这题我用扩展欧几里得去解的,为什么会wa呀?太菜了,想不明白错在哪里了呀,麻烦各位帮忙看看可以吗?谢谢

wa:

#include<iostream>
#include<cmath>

using namespace std;

typedef long long ll;

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()
{
    ll a,b,m,n,l,x,y;
    cin>>a>>b>>m>>n>>l;
    ll d=exgcd(m-n,b-a,x,y)%l;
    if((b-a)%d){
        cout<<"Impossible"<<endl;
        return 0;
    }
    b=abs(b-a);
    x=x*(b/d)%l;
    l=abs(l/d);
    while(x<0)x+=l;
    cout<<x%l<<endl;
    return 0;
}


活动打卡代码 AcWing 878. 线性同余方程

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;

ll exgcd(int a,int b,int &x,int &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;
    cin>>t;
    while(t--){
        int a,b,m,x,y;
        cin>>a>>b>>m;
        ll d=exgcd(a,m,x,y);
        if(b%d==0)cout<<(ll)x*(b/d)%m<<endl;
        else cout<<"impossible"<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 878. 线性同余方程

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;

ll exgcd(int a,int b,int &x,int &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;
    cin>>t;
    while(t--){
        int a,b,m,x,y;
        cin>>a>>b>>m;
        ll d=exgcd(a,m,x,y);
        if(b%d==0)cout<<(ll)x*(b/d)%m<<endl;
        else cout<<"impossible"<<endl;
    }
    return 0;
}



#include<iostream>
#include<algorithm>

using namespace std;

int exgcd(int a,int b,int &x,int &y)
{
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return d;
}

int main()
{
    int t,a,b,x,y;
    cin>>t;
    while(t--){
        cin>>a>>b;
        exgcd(a,b,x,y);
        cout<<x<<' '<<y<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 876. 快速幂求逆元

#pragma GCC optimize(3)
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;

ll quick_pow(ll x,ll y,ll mod)
{
    ll ans=1;
    while(y){
        if(y&1)ans=(ans*x)%mod;
        x=(x*x)%mod;
        y>>=1;
    }
    return ans%mod;
}

int main()
{
    ll t,a,b;
    cin>>t;
    while(t--){
        cin>>a>>b;
        ll ans=quick_pow(a,b-2,b)%b;
        if(a%b==0)cout<<"impossible"<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 875. 快速幂

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;

ll quick_pow(ll x,ll y,ll mod)
{
    ll ans=1;
    while(y){
        if(y&1)ans=(ans*x)%mod;
        x=(x*x)%mod;
        y>>=1;
    }
    return ans%mod;
}

int main()
{
    ll t,a,b,m;
    cin>>t;
    while(t--){
        cin>>a>>b>>m;
        cout<<quick_pow(a,b,m)<<endl;
    }
    return 0;
}



#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn=1e6+3;
int eulers[maxn],primes[maxn],cnt;
bool vis[maxn];

void get_eulers(int n)
{
    eulers[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            primes[cnt++]=i;
            eulers[i]=i-1;
        }
        for(int j=0;primes[j]<=n/i;j++){
            int t=primes[j]*i;
            vis[t]=true;
            if(i%primes[j]==0){
                eulers[t]=eulers[i]*primes[j];
                break;
            }
            eulers[t]=eulers[i]*(primes[j]-1);
        }
    }
}

int main()
{
    int n;
    cin>>n;
    get_eulers(n);
    long long sum=0;
    for(int i=1;i<=n;i++)sum+=eulers[i];
    cout<<sum<<endl;
    return 0;
}


活动打卡代码 AcWing 873. 欧拉函数

#include<iostream>

using namespace std;

int phi(int n)
{
    int res=n;
    for(int i=2;i<=n/i;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()
{
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        cout<<phi(n)<<endl;
    }
    return 0;
}