头像

LL26cH




离线:1天前


最近来访(71)
用户头像
不高兴的兽奶
用户头像
嘤雄达拉崩吧
用户头像
幽梦影情结
用户头像
zwling
用户头像
Kazimierz
用户头像
Dragonite
用户头像
InvolutionZ
用户头像
高某人
用户头像
霍斗
用户头像
BT7274
用户头像
AC别闹
用户头像
Zachary_
用户头像
每朝公式
用户头像
Zealone
用户头像
GabrielxD
用户头像
points233
用户头像
18910310021
用户头像
天元之弈
用户头像
林新月
用户头像
Hanson


LL26cH
6天前
#include<iostream>
using namespace std;

const int N=1000010;
int primes[N],st[N],phi[N],cnt;

long long g(int x)
{
    phi[1]=1;
    for(int i=2;i<=x;i++)
    {
        if(!st[i])
        {
            primes[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;primes[j]<=x/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0)
            {
                phi[primes[j]*i]=phi[i]*primes[j];
                break;   
            }
            phi[primes[j]*i]=phi[i]*(primes[j]-1);
        }
    }
    long long res=0;
    for(int i=1;i<=x;i++)res+=phi[i];
    return res;
}


int main()
{
    int n;
    cin>>n;

    cout<<g(n)<<endl;

    return 0;
}


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

LL26cH
7天前
#include<iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        int res=x;
        for(int i=2;i<=x/i;i++)
        {
            if(x%i==0)res=res-res/i;
            //res=res*(1-1/i);
            while(x%i==0)x/=i;
        }
        if(x>1)res=res-res/x;
        cout<<res<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 872. 最大公约数

LL26cH
8天前
#include<iostream>
using namespace std;

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
    // while(b!=0)
    // {
    //     a%=b;
    //     swap(a,b);
    // }
    // return a;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<gcd(a,b)<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 871. 约数之和

LL26cH
8天前
#include<iostream>
#include<unordered_map>
using namespace std;

const int mod=1e9+7;

int main()
{
    unordered_map<int,int> primes;

    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++)
        {
            while(x%i==0)
            {
                x/=i;
                primes[i]++;
            }
        }
        if(x>1)primes[x]++;
    }

    long long res=1;

    for(pair<int,int> prime:primes)
    {
        long long t=1;
        int p=prime.first,a=prime.second;
        while(a--)t=(t*p+1)%mod;
        res=res*t%mod;
    }
    cout<<res<<endl;

    return 0;
}


活动打卡代码 AcWing 870. 约数个数

LL26cH
9天前
#include<iostream>
#include<unordered_map>
using namespace std;

const int mod=1e9+7;

int main()
{
    int n;
    cin>>n;
    unordered_map<int,int> primes;
    while(n--)
    {
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++)
            while(x%i==0)
            {
                primes[i]++;
                x/=i;
            }
        if(x>1)primes[x]++;
    }
    long long res=1;
    for(pair<int,int> prime:primes) res=res*(prime.second+1)%mod;
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 869. 试除法求约数

LL26cH
10天前
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

void d(int x)
{
    vector<int> res;
    for(int i=1;i<=x/i;i++)
    {
        if(x%i==0)
        {
            res.push_back(i);
            if(i!=x/i)res.push_back(x/i);
        }
    }
    sort(res.begin(),res.end());
    for(int i:res)cout<<i<<' ';
    cout<<endl;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        d(x);
    }
    return 0;
}


活动打卡代码 AcWing 868. 筛质数

LL26cH
10天前
#include<iostream>
using namespace std;

const int N=1000010;

int primes[N],st[N],cnt;

void g(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(primes[j]%i==0)break;
        }
    }
}

int main()
{
    int n;
    cin>>n;
    g(n);
    cout<<cnt<<endl;
    return 0;
}


活动打卡代码 AcWing 867. 分解质因数

LL26cH
10天前
#include<iostream>
using namespace std;

void d(int x)
{
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)
        {
            int s=0;
            while(x%i==0)
            {
                x/=i;
                s++;
            }
            cout<<i<<' '<<s<<endl;
        }
    }
    if(x>1)cout<<x<<' '<<1<<endl;
    cout<<endl;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        d(x);
    }   
    return 0;
}



LL26cH
11天前
#include<iostream>
using namespace std;


bool is_prime(int x)
{
    if(x<2)return false;
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)return false;
    }
    return true;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        if(is_prime(x))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}



LL26cH
12天前
#include<iostream>
using namespace std;

const int N=510,M=100010;

int h[M],e[M],ne[M],idx;

int match[N];
bool st[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool find(int x)
{
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            st[j]=true;
            if(match[j]==0||find(match[j]))
            { //如果被确定了,就去看它的对面能不能去确定另外一个,如果不能就无法成功
                match[j]=x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int n1,n2,m;
    cin>>n1>>n2>>m;

    for(int i=0;i<N;i++)h[i]=-1;

    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    int res=0;

    for(int i=1;i<=n1;i++)
    {
        for(int j=0;j<N;j++)st[j]=0;
        if(find(i))res++;
    }
    cout<<res<<endl;
    return 0;
}