头像

mesopotamian


访客:3159

离线:9小时前


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

mesopotamian
2个月前
#include <iostream>

#include <algorithm>
typedef long long LL;
using namespace std;

const int N = 5e4+10;
int fcnt;
struct Factor
{
    int p,s;
}factor[1601];

int prime[N],cnt;
bool st[N];
void init(int n)
{
    for(int i = 2; i <= n; ++i)
    {
        if(!st[i]) prime[cnt ++] = i;
        for(int j = 0; prime[j] * i <= n; ++j)
        {
            st[prime[j] * i] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}

int dividor[N],dcnt;
void dfs(int u,int p)
{
    if(u == fcnt)
    {
        dividor[dcnt ++] = p;
        return;
    }
    for(int i = 0; i <= factor[u].s; ++i)
    {
        dfs(u + 1, p);
        p *= factor[u].p;
    }
}
int main()
{
    init(N-1);
    int n; cin >> n;
    while(n--)
    {
        int a,b,c,d;
        cin >> a >> b >> c >> d;

        fcnt = 0;

        int t = d;
        for(int i = 0; prime[i] <= t / prime[i]; i ++)
        {
            int p = prime[i];
            if(t % p == 0)
            {
                int s = 0;
                while(t % p == 0) t /= p, s ++;
                factor[fcnt ++] = {p,s};
            }
        }
        if(t > 1) factor[fcnt ++] = {t, 1};

        dcnt = 0;
        dfs(0, 1);

        int res = 0;
        for(int i = 0; i < dcnt; ++i)
        {
            int x = dividor[i];
            if(__gcd(a, x) == b && (LL)c * x / __gcd(c, x) == d) res ++;
        }
        cout << res << '\n';
    }
}


活动打卡代码 AcWing 1291. 轻拍牛头

mesopotamian
2个月前
#include <iostream>
using namespace std;
const int N = 1e6+10;
int a[N],cnt[N],s[N];
int main()
{
    int n; 
    scanf("%d",&n);
    for(int i = 0; i < n; ++i)
    {
        scanf("%d",&a[i]);
        cnt[a[i]] ++;
    }
    for(int i = 1; i < N; ++i)
        for(int j = i; j < N; j += i)
            s[j] += cnt[i];
    for(int i = 0; i < n; ++i) printf("%d\n",s[a[i]] - 1);
}


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

mesopotamian
2个月前
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
int prime[N],cnt;
bool st[N];
void init(int n)
{
    memset(st,0,sizeof st);
    cnt = 0;
    for(int i = 2; i <= n; ++i)
    {
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0; prime[j] * i <= n; ++i)
        {
            st[prime[j]*i] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}
int main()
{
    int l,r;
    while(cin >> l >> r)
    {
        init(50000);
        memset(st,0,sizeof st);
        for(int i = 0; i < cnt; ++i)
        {
            LL p = prime[i];
            for(LL j = max(p*2,(l + p - 1) / p * p); j <= r; j += p)
                st[j - l] = 1;
        }
        cnt = 0;
        for(int i = 0; i <= r - l; ++i)
            if(!st[i] && i + l >= 2) prime[cnt++] = i + l;
        if(cnt < 2) puts("There are no adjacent primes.");
        else
        {
            int minp = 0,maxp = 0;
            for(int i = 0; i + 1 < cnt; ++i)
            {
                int d = prime[i+1]-prime[i];
                if(d < prime[minp+1] - prime[minp]) minp = i;
                if(d > prime[maxp+1] - prime[maxp]) maxp = i;
            }
            printf("%d,%d are closest, %d,%d are most distant.\n",
            prime[minp],prime[minp+1],
            prime[maxp],prime[maxp+1]);
        }

    }
}



mesopotamian
2个月前
#include <cstdio>

const int N = 1e5+10;
int prime[N],cnt;
bool st[N];
void init(int n)
{
    for(int i = 2; i <= n; ++i)
    {
        if(!st[i]) prime[cnt ++] = i;
        for(int j = 0; prime[j] * i <= n; ++j)
        {
            st[prime[j] * i] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    init(n + 1);
    if(n <= 2) puts("1");
    else puts("2");
    for(int i = 2; i <= n + 1; ++i)
    {
        if(st[i]) printf("2 ");
        else printf("1 ");
    }
}


活动打卡代码 AcWing 1292. 哥德巴赫猜想

mesopotamian
2个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int prime[N],cnt;
int vis[N];

void init(int n)
{
    for(int i = 2; i <= n; ++i)
    {
        if(!vis[i]) prime[cnt++] = i;
        for(int j = 0; prime[j]*i <= n; ++j)
        {
            vis[prime[j]*i] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}
int main()
{
    init(N-1);
    int n;
    while(cin >> n,n)
    {
        for(int i = 1; ; ++i)
        {
            int a = prime[i];
            int b = n - a;
            if(!vis[b])
            {
                printf("%d = %d + %d\n",n,a,b);
                break;
            }
        }
    }
}



mesopotamian
2个月前

求s的时候有可以正着求,也可以倒着求,注意正着求可能会爆int 用long long 存

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int prime[N],cnt;
bool st[N];

int init(int n)
{
    for(int i = 2; i <= n; ++i)
    {
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0; prime[j] * i <= n; ++j)
        {
            st[prime[j] * i] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    init(n);
    for(int i = 0; i < cnt; ++i)
    {
        int p = prime[i];
        int s = 0;
        //for(int j = n; j > 0; j /= p) s +=  j / p;
        for(long long j = p; j <= n; j *= p) s += (n / j); // 注意正着写的话要开long long 不然可能会溢出
        cout << p << ' ' << s << '\n';
    }
}


活动打卡代码 AcWing 1171. 距离

mesopotamian
3个月前
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5+10, M = 2e5+10;
int vis[N],h[N],tot,fa[N],dis[N],res[M];
vector<PII> query[N];
struct Edge{
    int to,nxt,w;
}e[M];

int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void add(int from,int to,int w)
{
    e[tot].to = to, e[tot].w = w, e[tot].nxt = h[from];
    h[from] = tot ++;
}
void dfs(int u,int fa)
{
    for(int i = h[u]; ~i; i = e[i].nxt)
    {
        int to = e[i].to;
        if(to == fa) continue;
        dis[to] = dis[u] + e[i].w;
        dfs(to,u);
    }
}
void tarjan(int u)
{
    vis[u] = 1;
    for(int i = h[u]; ~i; i = e[i].nxt)
    {
        int to = e[i].to;
        if(!vis[to])
        {
            tarjan(to);
            fa[to] = u;
        }
    }
    for(auto item : query[u])
    {
        int y = item.first, id = item.second;
        if(vis[y] == 2)
        {
            int anc = find(y);
            res[id] = dis[y] + dis[u] - dis[anc]*2;
        }
    }
    vis[u] = 2;
}
int main(){
    int n,m;
    memset(h, -1, sizeof h); tot = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) fa[i] = i;
    for(int i = 0; i < n - 1; ++i)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c); add(b,a,c);
    }
    for(int i = 0,a,b; i < m; ++i)
    {
        cin >> a >> b;
        if(a != b)
        {
            query[a].push_back({b,i});
            query[b].push_back({a,i});
        }
    }
    dfs(1,-1);
    tarjan(1);
    for(int i = 0; i < m; ++i) printf("%d\n",res[i]);
    return 0;
}


活动打卡代码 AcWing 1172. 祖孙询问

mesopotamian
3个月前
#include <bits/stdc++.h>
using namespace std;
const int N = 4e4+10, M = N * 2;

struct Edge{
    int to,nxt;
}e[M];
int h[N],tot,depth[N],fa[N][16],q[N];
void add(int from,int to)
{
    e[tot].to = to,e[tot].nxt = h[from];
    h[from] = tot ++ ;
}
void bfs(int rt)
{
    /*
        预处理depth fa 数组
        设置 哨兵
    */
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[rt] = 1;
    q[0] = rt;
    int hh = 0, tt = 0;
    while(hh <= tt)
    {
        int u = q[hh ++];
        for(int i = h[u]; ~i; i = e[i].nxt)
        {
            int to = e[i].to;
            if(depth[to] > depth[u] + 1)
            {
                depth[to] = depth[u] + 1;
                q[++ tt] = to;
                fa[to][0] = u;
                for(int k = 1; k <= 15; ++k)
                    fa[to][k] = fa[fa[to][k-1]][k-1];
            }
        }
    }
}
int lca(int a,int b)
{
    if(depth[a] < depth[b]) swap(a,b);
    for(int k = 15; k >= 0; k--)
        if(depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if(a == b) return a;
    for(int k = 15; k >= 0; k--)
    {
        if(fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}
int main()
{
    memset(h, -1, sizeof h); tot = 0;
    int m; cin >> m;
    int rt = 0;
    while(m--)
    {
        int a,b;
        cin >> a >> b;
        if(b == -1) rt = a;
        else add(a,b),add(b,a);
    }
    bfs(rt);
    cin >> m;
    while(m--)
    {
        int a,b; cin >> a >> b;
        int p = lca(a,b);
        if(p == a) puts("1");
        else if(p == b) puts("2");
        else puts("0");
    }
}



mesopotamian
3个月前
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 510, M = 1e4+10;
int n,m;
int tot,h[N],d[N][N][2],fa[N];
struct Edge{
    int to,nxt,w;
}e[M << 1];
struct node{
    int a,b,w,f;
    bool operator<(const node&b)
    {
        return w < b.w;
    }
}edge[M << 1];
int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void add(int from,int to,int w)
{
    e[tot].to = to, e[tot].w = w, e[tot].nxt = h[from];
    h[from] = tot ++;
}
void dfs(int rt,int u,int fa,int m1,int m2)
{
   d[rt][u][0] = m1;
   d[rt][u][1] = m2;
   for(int i = h[u]; ~i; i = e[i].nxt)
   {
       int to = e[i].to;
       if(to == fa) continue;
       m1 = d[rt][u][0], m2 = d[rt][u][1];
       if(e[i].w > m1) m2 = m1,m1 = e[i].w;
       else if(e[i].w < m1 && e[i].w > m2) m2 = e[i].w;
       dfs(rt,to,u,m1,m2);
   }

}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h); tot = 0;
    for(int i = 1; i <= n; ++i) fa[i] = i;
    for(int i = 0; i < m; ++i)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edge[i] = {a,b,w};
    }
    sort(edge,edge+m);
    LL sum = 0;
    for(int i = 0; i < m; ++i)
    {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;
        int f1 = find(a), f2 = find(b);
        if(f1 != f2)
        {
            fa[f1] = f2;
            sum += w;
            add(a,b,w); add(b,a,w);
            edge[i].f = true;
        }
    }
    for(int i = 1; i <= n; ++i) dfs(i,i,-1,0,0);
    LL res = 1e18;
    for(int i = 0; i < m; ++i)
    {
        if(!edge[i].f)
        {
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;
            LL t;
            if(w > d[a][b][0]) t = sum + w - d[a][b][0];
            else if(w > d[a][b][1]) t = sum + w - d[a][b][1];
            res = min(res,t);
        }
    }
    printf("%lld\n",res);
    return 0;
}



mesopotamian
3个月前

Snipaste_2020-02-24_18-13-06.png
(0).(0) 999ms

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4+10, M = 2e5+10;
struct Edge{
    int to,nxt,w;
}e[M];
struct node{
    int to,w;
    bool operator<(const node &b)const
    {
        return w > b.w;
    }
};
int tot,h[N],dis[6][N],in[N],vis[N],ans = 0x3f3f3f3f;
vector<int> adds;
int n,m;
void add(int from,int to,int w)
{
    e[tot].to = to, e[tot].w = w, e[tot].nxt = h[from];
    h[from] = tot ++ ;
}
int dij(int pos)
{
    memset(in,0,sizeof in);
    int s = adds[pos];
    priority_queue<node> q;
    q.push({s,0}); dis[pos][s] = 0;
    while(q.size())
    {
        int fa = q.top().to; q.pop();
        if(in[fa]) continue;
        in[fa] = 1;
        for(int i = h[fa]; ~i; i = e[i].nxt)
        {
            int to = e[i].to;
            if(dis[pos][to] > dis[pos][fa] + e[i].w)
            {
                dis[pos][to] = dis[pos][fa] + e[i].w;
                q.push({to,dis[pos][to]});

            }
        }
    }
}
void dfs(int cnt,int u,int distance)
{
    if(cnt == 5)
    {
        ans = min(ans,distance);
        return;
    }
    for(int i = 1; i < 6; ++i)
    {
        if(vis[i]) continue;
        vis[i] = 1;
        dfs(cnt+1,i,distance + dis[u][adds[i]]);
        vis[i] = 0;
    }
}
int main()
{
    memset(h, -1, sizeof h); tot = 0;
    cin >> n >> m;
    adds.push_back(1);
    for(int i = 0,x; i < 5; ++i)
    {
        cin >> x;
        adds.push_back(x);
    }

    for(int i = 0, a, b, c; i < m; ++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c); add(b,a,c);
    }
    memset(dis, 0x3f, sizeof dis);
    for(int i = 0; i < 6; ++i)dij(i);
    dfs(0,0,0);
    cout << ans;
    return 0;
}