头像

2x2v1134


访客:9286

离线:9天前


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

2x2v1134
4个月前
//这里填你的代码^^
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
    int n;
    cin>>n;
    int res=1;
    ll ai;
    for(int i=0;i<n;i++)
    {
        cin>>ai;
        res=ai;
        for(int j=2;j*j<=ai;j++)
        {
            if(ai%j==0)
            {
                res=res/j*(j-1);
                while(ai%j==0)
                {
                    ai=ai/j;
                }
            }
        }
        if(ai>1)
        {
            res=res/ai*(ai-1);
        }
        cout<<res<<endl;
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

2x2v1134
4个月前
//这里填你的代码^^
#include<iostream>
using namespace std;
typedef long long ll;
int gcd(ll a,ll b)
{
    if((b%a)==0)
    {
        //cout<<"out"<<endl;
        //cout<<b<<" "<<a<<endl;
        return a;
    }
        //cout<<(b%a)<<endl;
    return gcd(b%a,a);
}
int main()
{
    int n;
    cin>>n;
    ll a,b;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        if(a>b)
        {
            int temp=a;
            a=b;
            b=temp;
        }
        //cout<<a<<" "<<b<<endl;
        int res=gcd(a,b);

        cout<<res<<endl;
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

2x2v1134
4个月前
//这里填你的代码^^
#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long ll;
ll mod=(1e+9)+7;
ll powera(ll a,int b)
{

    ll res=1;
    for(;b;b=b>>1)
    {
        if(b&1)
        {
            res=res*a;
        }
        a=a*a;
    }
    //cout<<res;
    //return 1;
    return res;
}
int main()
{
    unordered_map<ll,int>prime;
    int n;
    cin>>n;
    ll ai;
    for(int i=0;i<n;i++)
    {
        cin>>ai;
        for(ll j=2;j*j<=ai;j++)
        {
            while(ai%j==0)
            {
                prime[j]++;
                ai=ai/j;
            }
        }
        if(ai>1)
        {
            prime[ai]++;
        }
    }
    ll res=1;
    for(auto p:prime)
    {
        //cout<<p.first<<" "<<p.second<<endl;
        //res=(res*(powera(p.first,p.second+1)-1)/(p.first-1))%mod;
        ll a=p.first;
        ll t=1;
        int b=p.second;
        while(b--)
        {
            t=(t*a+1)%mod;
        }
        res=(res*t)%mod;
    }
    cout<<res;
    return 0;

}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

2x2v1134
4个月前
//这里填你的代码^^
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=110;
ll num[N];
int mod=(1e+9)+7;

int main()
{
    ll maxai=0;
    int n;
    ll a;
    cin>>n;
    unordered_map<int,int>prime;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        for(ll i=2;i*i<=a;i++)
        {
            while(a%i==0)
            {
                a=a/i;
                prime[i]++;
            }

        }
        if(a>1)
            {
                prime[a]++;
            }
    }
    ll res=1;
    for(auto p:prime)
    {
        res=res*(p.second+1)%mod;
    }
    //int res=numOfDivi(maxai,n);
    cout<<res;
    return 0;
}

//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

2x2v1134
4个月前
//这里填你的代码^^
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void printDivi(int ai)
{
    vector<int>divi;
    for(int i=1;i<=ai/i;i++)
    {
        if(ai%i==0)
        {

            divi.push_back(i);
            if(i*i!=ai)
            {
                divi.push_back(ai/i);
            }
        }
    }
    sort(divi.begin(),divi.end());
    for(int i=0;i<divi.size();i++)
    {
        cout<<divi[i]<<" ";
    }
    cout<<endl;
}
int main()
{
    int n;
    cin>>n;
    int ai;
    for(int i=0;i<n;i++)
    {
        cin>>ai;
        printDivi(ai);
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

2x2v1134
4个月前
//这里填你的代码^^
#include<iostream>
using namespace std;
const int N=1000010;
int prime[N];
int st[N];
int numOfPrime(int n)
{
    int count=0;
    int j=0;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            //out<<"prime : "<<i<<endl;
            prime[j++]=i;
            count++;
        }
        for(int p=0;p<=j&&(prime[p]<=n/i);p++)
        {
            st[prime[p]*i]=1;
            if(i%prime[p]==0)
            {
                break;
            }
        }
    }
    return count;
}
int main()
{
    int n;
    cin>>n;
    int res=numOfPrime(n);
    cout<<res;
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



2x2v1134
4个月前
//这里填你的代码^^
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int M=100010,N1=510,N2=510;
int r[M],l[M],headr[N2],headl[N1],nel[M],ner[M],mapl_r[N1],mapr_l[N2],usedr[N2];
int idx=1;

void add_left_to_right(int nodel,int noder)
{
    r[idx]=noder,nel[idx]=headl[nodel],headl[nodel]=idx++;
}
/*
void add_right_to_left(int noder,int nodel)
{
    l[idx]=nodel,ner[idx]=headr[noder],headr[noder]=idx++;
}
*/
bool IfUpdate(int node,char mode)
{

    if(mode=='l')
    {
        for(int p=headl[node];p!=0;p=nel[p])
        {
            if(mapr_l[r[p]]==0)
            {
                mapr_l[r[p]]=node;
                mapl_r[node]=r[p];
                return true;
            }
        }
        for(int p=headl[node];p!=0;p=nel[p])
        {
            int prenode_map_rp=mapr_l[r[p]];
            //mapl_r[node]=r[p];
            //mapr_l[r[p]]=node;
            if(usedr[r[p]]==0){
                usedr[r[p]]=1;
                if(IfUpdate(prenode_map_rp,'l'))
                {
                    //mapr_l[l[p]]=node;
                    mapl_r[node]=r[p];
                    mapr_l[r[p]]=node;
                    return true;
                }
            }
        }
    }
    return false;  
}
int maxMap(int n1,int n2)
{
    //
    int count=0;
    for(int i=1;i<=n1;i++)
    {
        //cout<<i<<endl;
        //if((mapl_r[i]==0)&&headl[i]!=0)
        {
            if(IfUpdate(i,'l'))
            {
               count++; 
            }
        }
    }
    //cout<<n1<<n2<<endl;
    return count;
}
int main()
{
    int n1,n2,m;
    cin>>n1>>n2>>m;
    int lnode,rnode;
    for(int i=0;i<m;i++)
    {
        cin>>lnode>>rnode;
        add_left_to_right(lnode,rnode);
        //add_right_to_left(rnode,lnode);
    }
    //int res=1;
    int res=maxMap(n1,n2);
    cout<<res;
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

2x2v1134
4个月前
//这里填你的代码^^
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;



/*
void buildPrime(ll ai)
{
    for(ll i=3;i<=ai;i++)
    {
        bool IsPrime=true;
        for(ll j=2;j*j<=i;j++)
        {
            if(i%j==0)
            {
                IsPrime=false;
                break;
            }
        }
        if(IsPrime)
        {
            PrimeV[index_prime]=i;
            //cout<<"Prime"<<index_prime<<" "<<i<<endl;
            index_prime++;
        }
    }
}
*/
void divide(ll ai)
{
    for(int i=2;i*i<=ai;i++)
    {
        if(ai%i==0)
        {
            int s=0;
            while(ai%i==0)
            {
                ai=ai/i;
                s++;
            }
            cout<<i<<" "<<s<<endl;
        }

    }
    if(ai>1)
    {
        cout<<ai<<" "<<1<<endl;
    }
    cout<<endl;
}

int main()
{
    int n;
    cin>>n;
    ll aii;
    ll maxai=0;
    for(int i=0;i<n;i++)
    {
        cin>>aii;
        divide(aii);
        //cout<<Nu;m[i]<<" "<<"num"<<endl;
    }

    return 0;
}

//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



2x2v1134
4个月前
//这里填你的代码^^
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=100010,M=200020;
int e[M],head[M],ne[M],color[N];
int idx=1;

void add(int node1,int node2)
{
    e[idx]=node2,ne[idx]=head[node1],head[node1]=idx++;
}

bool dfsColor(int node,int nodeindex)
{
    //cout<<node<<" node "<<nodeindex<<endl;
    if(color[node]==3-nodeindex)
    {
        return false;
    }
    if(color[node]==nodeindex)
    {
        return true;
    }
    if(color[node]==0)
    {
        color[node]=nodeindex;
    }
    for(int p=head[node];p!=0;p=ne[p])
    {   
        //if(color[e[p]]==0)
        {
            if(!dfsColor(e[p],3-nodeindex))
            {
                return false;
            }
        }
    }
    //color[node]=nodeindex;
    return true;
}
int main()
{
    int n,m;
    cin>>n>>m;
    int x,y;
    for(int i=0;i<m;i++)
    {
        cin>>x>>y;
        add(x,y);
        add(y,x);

    }

    //bool res=splittwograph(n,m);
    bool res=true;
    for(int i=1;i<=n;i++)
    {
        if(color[i]==0)
        {
            if(!dfsColor(i,1))
            {
                res=false;
            }
        }
    }
    if(res)
    {
        cout<<"Yes";
    }
    else 
    {
        cout<<"No";
    }
    return 0;
}




//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



2x2v1134
4个月前
//这里填你的代码^^
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N =100010,M=200020;
int vec[N];
struct edge{
    int node1;
    int node2;
    int dis;
    bool operator < (const edge &W) const
    {
        return dis<W.dis;
    }
}edges[M];

int father(int node)
{
    if(vec[node]!=node)
    {
        vec[node]=father(vec[node]);

    }
    return vec[node];
}
int main()
{
    int n,m;
    cin>>n>>m;
    int x,y,z;
    int res=0;
    for(int i=0;i<m;i++)
    {
        cin>>x>>y>>z;
        edges[i]={x,y,z};
    }
    sort(edges,edges+m);

    for(int i=1;i<=n;i++)
    {
        vec[i]=i;
    }
    int count=0;
    for(int i=0;i<m;i++)
    {
        int nodea=father(edges[i].node1);
        int nodeb=father(edges[i].node2);
        //cout<<"nodea"<<" "<<"nodeb"<<endl;
        //cout<<edges[i].node1<<" "<<nodea<<" "<<edges[i].node2<<""nodeb<<endl;
        if(nodea!=nodeb){
            vec[nodea]=nodeb;
            res=res+edges[i].dis;
            count++;
        }
        /*
        for(int j=1;j<=n;j++)
        {
            cout<<vec[j]<<" ";
        }
        cout<<endl;
        */
    }
    if(count==n-1)
    {
        cout<<res<<endl;
    }
    else
    {
        cout<<"impossible";
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~