Acwing第 59 场周赛(AK)

4492. 减法操作

给定一个整数 $n$，执行如下算法：

1. 如果 $n=0$，则结束算法。
2. 找到 $n$ 的最小质因子 $d$。
3. 令 $n$ 减去 $d$ 并跳转步骤 $1$。

请你计算，在算法执行的过程中，一共进行了多少次减法操作。

输入格式

一个整数 $n$。

输出格式

一个整数，表示减法操作的次数。

数据范围

所有测试点满足 $2\le n\le 10^{10}$

/* A: 10min B: 20min C: 30min D: 40min */ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <assert.h>
#include <sstream>
#define pb push_back 
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){
    for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {
    if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<long long ,long long >PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+10,M=1e9+7;

ll n,cnt;
// 判断n是不是质数
bool is_prime(ll n) {
    
    if (n == 1) return false;
    for (ll i = 2; i * i <= n; i++) {
    
        if (n % i == 0) return false;
    }
    return true;
}
void solve(){
    
    cin>>n;
    if(!is_prime(n)){
    
        if(n&1){
    
            // 求n的最小质因子
            ll x=n;
            ll i;
            for( i=2;i*i<=x;i++){
    
                if(x%i==0){
    
                    break;
                }
            }
            cout<<1+(x-i)/2<<endl;
        }
        else
            cout<<n/2;
    }
    else{
    
        cout<<1;
    }
}

int main(){
    
    solve();
	return 0;
}

4493. 环形连通分量

并查集水题，题意模拟就行

/* A: 10min B: 20min C: 30min D: 40min */ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <assert.h>
#include <sstream>
#define pb push_back 
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){
    for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {
    if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<long long ,long long >PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=4e5+10,M=1e9+7;

int n,m;
int h[N],e[N],ne[N],idx;
int cnt;
vector<int>g[N];
int fa[N];
void add(int a,int b){
    
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

int find(int u){
    
    return fa[u]==u?u:fa[u]=find(fa[u]);
}

void merge(int u,int v){
    
    int fu=find(u),fv=find(v);
    if(fu==fv)return;
    fa[fu]=fv;
}
int d[N];
void solve(){
       
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    fo(i,1,n)fa[i]=i;
    fo(i,1,m){
    
        int u,v;cin>>u>>v;
        add(u,v);add(v,u);
        d[u]++;
        d[v]++;
        merge(u,v);
    }
    fo(i,1,n){
    
        g[find(i)].pb(i);
    }
    // fo(i,1,n){
    
    // cout<<i<<" "<<g[i].size()<<endl;
    // }
    for(int i=1;i<=n;i++){
    
        if(g[i].size()>=3){
    
            bool flag=1;
            for(auto c:g[i]){
    
                if(d[c]!=2){
    
                    flag=0;
                    break;
                }
            }
            if(flag){
    
                cnt++;
            }
        }
    }
    cout<<cnt<<endl;
}

int main(){
    
    solve();
	return 0;
}