头像

大大怪




离线:53分钟前


最近来访(14)
用户头像
xxdxs
用户头像
kyo
用户头像
leo123456
用户头像
Belous
用户头像
sky_6
用户头像
衣笠傻白
用户头像
Q_W_Q
用户头像
白金之星
用户头像
ZurichRain
用户头像
森屿弥鹿
用户头像
minnn

活动打卡代码 AcWing 791. 高精度加法

#include<iostream>
#include<vector>
using namespace std;
vector<int> add(vector<int> &a,vector<int> &b)
{
    int t=0;
    vector<int> c;
    for(int i=0;i<a.size()||i<b.size();i++)
    {
        if(i<a.size())
            t+=a[i];
        if(i<b.size()) t+=b[i];
        c.push_back(t%10);
        t/=10;
    }
    if(t) c.push_back(t);
    return c;
}
int main()
{
    string tem1,tem2;
    vector<int> a,b;
    cin>>tem1>>tem2;
    for(int i=tem1.size()-1;i>=0;i--) a.push_back(tem1[i]-'0');
    for(int i=tem2.size()-1;i>=0;i--) b.push_back(tem2[i]-'0');
    auto c=add(a,b);
    for(int i=c.size()-1;i>=0;i--) cout<<c[i];
}


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

大大怪
16天前
#include<iostream>
using namespace std;
int main()
{
    int n;
    scanf("%d",&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;
                while(x%i==0) x/=i;
            }
        }
        if(x>1) res=res-res/x;
        cout<<res<<endl;
    }
}


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

大大怪
16天前
#include<iostream>
using namespace std;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }

    return 0;
}


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

大大怪
22天前


#include<iostream>
#include<unordered_map>
using namespace std;
const int mod=1e9+7;
int main()
{
    int n;
    scanf("%d",&n);
    unordered_map<int,int > m;
    while(n--)
    {
        int x;
        scanf("%d",&x);
        for(int i=2;i<=x/i;i++)
        {
            while(x%i==0)
            {
                m[i]++;
                x/=i;
            }
        }
        if(x>1) m[x]++;
    }
    // long long temp=1;
    long long res=1;
    for(auto t:m)
    {
        long long temp=1;
        while(t.second--)
        {
            temp=temp*t.first+1;
            temp%=mod;
        }
        res*=temp;
        res%=mod;
    }
    cout<<res;
}


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

大大怪
22天前
约数个数=(a1+1)(a2+1)(a3+1)....(ak+1)


#include<iostream>
#include<unordered_map>
using namespace std;
const int mod=1e9+7;
int main()
{
    int n;
    scanf("%d",&n);
    unordered_map<int,int> m;//比map查找更快
    while(n--)
    {
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++)
        {
            while(x%i==0)
            {
                m[i]++;
                x/=i;
            }
        }
        if(x>1) m[x]++;
    }
    long long res=1;
    for(auto t:m)
    {
        res=res*(t.second+1);
        res%=mod;
    }
    cout<<res;
} 



大大怪
22天前
#include<iostream>
#include<unordered_map>
using namespace std;
const int mod=1e9+7;
int main()
{
    int n;
    scanf("%d",&n);
    unordered_map<int,int> m;//比map查找更快
    int a=1;
    while(n--)//先把所有数乘起来
    {
        int x;
        cin>>x;
        a*=x;
    }


    int x=a;
    for(int i=2;i<=x/i;i++)
        {
            while(x%i==0)
            {
                m[i]++;
                x/=i;
            }
        }
        if(x>1) m[x]++;
    long long res=1;
    for(auto t:m)
    {
        res=res*(t.second+1);
        res%=mod;
    }
    cout<<res;
}


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

大大怪
22天前
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void get_divisors(int x)
{
    vector<int> d;
    for(int i=1;i<=x/i;i++)
    {
        if(x%i==0)
        {
            d.push_back(i);
            if(i!=x/i) d.push_back(x/i);
        }
    }
    sort(d.begin(),d.end());
    for(int i=0;i<d.size();i++)
    {
        printf("%d ",d[i] );

    }
    printf("\n");
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int x;
        cin>>x;
        get_divisors(x);

    }
}


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

大大怪
23天前
#include<iostream>
using namespace std;

const int N=1000010;
int prime[N];
bool st[N];
int main()
{
    int x;
    scanf("%d",&x);
    int cnt=0;
    for(int i=2;i<=x;i++)
    {
        if(!st[i]) prime[cnt++]=i;
        for(int j=i+i;j<=x;j+=i)//把这个数的所有倍数都去除
        {
            st[j]=true;
        }
    }
    cout<<cnt<<endl;
}

优化版(埃式算法)
#include<iostream>
using namespace std;
bool st[1000010];
int main()
{
    int n;
    scanf("%d",&n);
    int cnt=0;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            cnt++;
            for(int j=i+i;j<=n;j+=i)
            {
                st[j]=true;
            }
        }
    }
    cout<<cnt;
}

最快版
#include<iostream>
using namespace std;
bool st[1000010];
int primes[1000010];
int getprime(int x)
{
    int cnt=0;
    for(int i=2;i<=x;i++)
    {
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=x/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
    return cnt;
}
int main()
{
    int n;
    scanf("%d",&n);
    cout<<getprime(n);

}


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

大大怪
23天前
#include<iostream>
using namespace std;
void divide(int x)
{
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)
        {int s=0;
            while(x%i==0)
            {
                x/=i;
                s++;
            }
            printf("%d %d\n",i,s);
        }
    }
    if(x>1) printf("%d 1\n",x);//每个数存在最多一个大于根号n的质因子
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int x;
        scanf("%d",&x);
        divide(x);
        printf("\n");
    }
}


活动打卡代码 AcWing 839. 模拟堆

大大怪
27天前
#include<iostream>
#include<string.h>
using namespace  std;
const int N=100010;
int ph[N],hp[N],h[N];
int cnt;
void heap_swap(int a,int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
    swap(h[a],h[b]);
}
void down(int u)
{
    int t=u;
    if(u*2<=cnt && h[u]>h[u*2]) t=u*2;
    if(u*2+1<=cnt && h[t]>h[u*2+1]) t=u*2+1;
    if(u!=t){
        heap_swap(u,t);
        down(t);
    }
}
void up(int u)
{
    while(u/2>0&&h[u]<h[u/2])
    {
        heap_swap(u,u/2);
        u/=2;
    }
}
int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while (n -- )
    {
        char op[5];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            scanf("%d", &x);
            cnt ++ ;
            m ++ ;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, cnt);
            cnt -- ;
            down(1);
        }
        else if (!strcmp(op, "D"))
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, cnt);
            cnt -- ;
            up(k);
            down(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }
}