首页 > 其他分享 >牛客竞赛数学专题—整数分解与筛法

牛客竞赛数学专题—整数分解与筛法

时间：2022-11-09 19:56:49浏览次数：73  
标签：err 专题 const cout 筛法 int ll 牛客 define

题目 链接

A.青蛙的约会

statement: 两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙\(A\)和青蛙\(B\),并且规定纬度线上东经\(0\)度处为原点，由东往西为正方向，单位长度\(1\)米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是\(x\)，青蛙\(B\)的出发点坐标是\(y\)。青蛙\(A\)一次能跳\(m\)米，青蛙\(B\)一次能跳\(n\)米，两只青蛙跳一次所花费的时间相同。纬度线总长$ L$米。现在要你求出它们跳了几次以后才会碰面。

Solution: 其实就是一道裸的扩展欧几里得， 设t为跳的步数，根据题意可以列出方程： $m*t+x \equiv n*t+y \ (\ mod\ l)$

变形得到：\({（m-n）* t + l * k = y-x }\) ,\((k\in Z)\)
题目等价于求最小正整数解 \(t\)。套板子即可

Code: 
#include <bits/stdc++.h
using namespace std;
typedef long long int ll;
#define dbg(x...) do { cout << #x << " -> "; err(x); } while(0)
#define endl '\n'
#define  tententen ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
const ll N = 1e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
void err() { cout << endl;}
template
void err(const T &arg, const Ts &... args) {cout << arg << ' ';err(args...);}
ll ex_gcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll ans = ex_gcd(b, a % b, x, y);
    ll t = x;
    x = y;
    y = t - a / b * y;
    return ans;
}
void solve() {
    ll xx, yy, n, m, l, x, y;
    cin >> xx >> yy >> m >> n >> l;
    ll dis = n - m, c = xx - yy;
    if (dis < 0) {
        dis *= -1;
        c *= -1;
    }
    ll g = ex_gcd(dis, l, x, y);
    if (c % g) {
        puts("Impossible");
        return;
    }
    x *= (c / g);
    cout << (x % (l / g) + l / g) % (l / g) << endl;
}
int main() {
    tententen
    int T = 1;
    // cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

B.Sum of Consecutive Prime Numbers

statement:

一些正整数可以用一个或多个连续素数的和来表示。给出一个正整数 $ n$，有多少种不同的表示形式？

Solution: 一个比较经典的尺取法 ，首先把素数筛出来，然后尺取法计算贡献就行了，我还顺带离散化了一下询问，但是好像有点多余 Code: 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define dbg(x...) do { cout << #x << " -> "; err(x); } while(0)
#define endl '\n'
#define  tententen ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
const int N = 4e7 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
void err() { cout << endl;}
template
void err(const T &arg, const Ts &... args) {cout << arg << ' ';err(args...);}
int prime[N],tot=0;
bool not_prime[N];
int ans[N],res[N];
struct node{
    int num,id;
    bool operator < (const node &t)const{
        return num < t.num ;
    }
}a[N];
void divide(int N) {
    for (int i = 2; i <= N; ++i) {
        if (!not_prime[i]) {
            prime[++tot] = i;
        }
        for (int j = 1; j <= tot && i * prime[j] <= N; ++j) {
            not_prime[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}
void solve() {
    int t;
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        cin >> a[i].num;
        a[i].id = i;
    }
    sort(a + 1, a + 1 + t);
    int cnt = 0;
    for (int i = 1; i <= t; ++i) {
        cnt = 0;
        if (ans[a[i].num] != -1) {
            res[a[i].id] = ans[a[i].num];
            continue;
        }
        int l = 1, r = 1;
        int sum = prime[1];
        while (r <= tot && l <= r) {
            while (r <= tot && sum < a[i].num) {
                r++;
                sum += prime[r];
            }
            if (sum == a[i].num) {
                cnt++;
                sum -= prime[l];
                l++;
            } else {
                sum -= prime[l];
                l++;
            }
        }
        ans[a[i].num] = cnt;
        res[a[i].id] = cnt;
    }
    for (int i = 1; i <= t; ++i) {
        cout << res[i] << endl;
    }
}
int main() {
    tententen;
    int T = 1;
    // cin>>T;
    divide(N - 4);
    memset(ans, -1, sizeof(ans));
    while (T--) {
        solve();
    }
    return 0;
}

C.Prime Distance

statement: 给出区间$[L,R]$

你要找到区间中最接近的两个相邻素数\(C1\) 和\(C2\) \((L\leq C1 \le C2≤R)\)（即$ C2-C1$是最小值），
如果还有其他相距相同的对，请输出第一对。

你要找到区间中最接近的两个相邻素数\(D1\) 和\(D2\) \((L\leq D1 \le D2≤R)\)（即$ D2-D1$是最大值）尽可能远离。如果有距离相同的，再次选择第一对。

Solution: 首先不可以一开始预处理出所有的素数。而我们已知一个数是合数，

即必然存在两个因子\(d\)和\(n/d\)，假设\(d \leq n/d\)，则\(d \leq n/d\)，即\(n\)必然存在一个小于\(sqrt(n)\)的因子

所以先预处理出 \(sqrt(N)\)范围内的全部素数，那么就可以通过这些素数继续来筛选\(sqrt(N)-N\)内的的质数，然后对于每一个区间暴力即可

Code: 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define dbg(x...) do { cout << #x << " -> "; err(x); } while(0)
#define endl '\n'
#define  tententen ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
const ll N = 1e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
void err() { cout << endl;}
template
void err(const T &arg, const Ts &... args) {cout << arg << ' ';err(args...);}
int prime[N*10],tot=0;
bool not_prime[N*10];
int vis[N*20];
void divide(int N) {
    for (int i = 2; i <= N; ++i) {
        if (!not_prime[i]) {
            prime[++tot] = i;
        }
        for (int j = 1; j <= tot && i * prime[j] <= N; ++j) {
            not_prime[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}
void solve() {
    int l, r;
    cin >> l >> r;
    l=max( l, 2ll );
    int pre = 0, mn = inf, mx = 0, l1, l2, r1, r2, cnt = 0;
    if (r <= 1e5) {
        for (int i = l; i <= r; ++i) {
            if (!not_prime[i]) {
                cnt++;
                if (cnt == 1) {
                    pre = i;
                    continue;
                }
                if (i - pre < mn) {
                    l1 = pre, r1 = i;
                    mn = min(i - pre, mn);
                }
                if (i - pre > mx) {
                    l2 = pre, r2 = i;
                    mx = max(i - pre, mx);
                }
                pre = i;
            }
        }
    } else {
        for (int i = 1; i <= r - l + 1; ++i) {
            vis[i] = 0;
        }
        for (int i = 1; i <= tot && prime[i] <= r; ++i) {
            int pre = max((l - 1) / prime[i] + 1, 2ll), lst = r / prime[i];
            for (int j = pre; j <= lst; ++j) {
                vis[(ll) j * prime[i] - l + 1] = 1;
            }
        }
        for (int i = 1; i <= r - l + 1; ++i) {
            if (!vis[i]) {
                cnt++;
                if (cnt == 1) {
                    pre = i;
                    continue;
                }
                if (i - pre < mn) {
                    l1 = pre + l - 1, r1 = i + l - 1;
                    mn = min(i - pre, mn);
                }
                if (i - pre > mx) {
                    l2 = pre + l - 1, r2 = i + l - 1;
                    mx = max(i - pre, mx);
                }
                if(i+l!=2)pre = i;
            }
        }
    }
    if (cnt < 2) {
        cout << "There are no adjacent primes." << endl;
    } else {
        cout << l1 << "," << r1 << " are closest, " << l2 << "," << r2 << " are most distant." << endl;
    }
}
signed main() {
    tententen;
    int T = 1;
    cin >> T;
    divide((N - 1));
    while (T--) {
        solve();
    }
    return 0;
}

D1.Zero-One (Easy Version)

statement: 给你一个正整数 $n$ ，让你输出 $n−1$。

但输入并不是一个正整数 \(n\)，而是给出 \(k\)组 \(pi,ei\),\(n=p1^{e1}∗p2^{e2}∗...∗pk^{ek}\)，其中 \(pi\)为素数，且 $ pi > pi+1$ ,\({e_i>0}\)

输出时也需要按上述格式输出。

Solution： 水题 其实就是一个唯一分解定理的应用 Code： 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define dbg(x...) do { cout << #x << " -> "; err(x); } while(0)
#define endl '\n'
#define  tententen ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
const ll N = 1e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
void err() { cout << endl;}
template
void err(const T &arg, const Ts &... args) {cout << arg << ' ';err(args...);}
ll ksm(ll a, ll b) {ll ans = 1;while (b > 0) {if (b & 1) {ans = ans * a ;}a = a * a ;b >>= 1;}return ans;}
int prime[N],tot=0;
bool not_prime[N];
void divide(int N) {
    for (int i = 2; i <= N; ++i) {
        if (!not_prime[i]) {
            prime[++tot] = i;
        }
        for (int j = 1; j <= tot && i * prime[j] <= N; ++j) {
            not_prime[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}
string s;
int n,num;
void solve() {
    vector ans;
    num = 1;
    cin>>n;
    for (int i = 1, x, y; i <= n; ++i) {
        cin >> x >> y;
        num *= ksm(x, y);
    }
    num--;
    for (int i = tot; i >= 1; --i) {
        if (num % prime[i] == 0) {
            ans.push_back(prime[i]);
            int cnt = 0;
            while (num % prime[i] == 0) {
                cnt++, num /= prime[i];
            }
            ans.push_back(cnt);
        }
    }
    for (int i = 0; i < ans.size(); ++i) {
        cout << ans[i] << " \n"[i == ans.size() - 1];
    }
}
signed main() {
    tententen;
    int T = 1;
    cin >> T;
    divide((N - 1));
    while (T--) {
        solve();
    }
    return 0;
}

E. Conveyor

statement: 给一个正整数 $ x$，让你构造出一个长度为 $m+1$的序列 $a_0,a_1,a_2,...a_m $

其中 \(a_0=1,a_m=x,a_i<a_i+1\) ,\(a_i|a_{i+1}\)

求能构造出的序列中 \(m\)的最大值，以及 \(m\)等于最大值时的方案数

Solution: 分析题意，其实就是问将$x$所有因子的全排列有多少种当然还是要去重

\(n\)个不同的数的全排列除去重复的就是\(n!\)除以每个重复因子数的阶乘

Code: 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define dbg(x...) do { cout << #x << " -> "; err(x); } while(0)
#define endl '\n'
#define int ll
#define  tententen ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
const ll N = 1e3 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
void err() { cout << endl;}
template
void err(const T &arg, const Ts &... args) {cout << arg << ' ';err(args...);}
ll ksm(ll a, ll b) {ll ans = 1;while (b > 0) {if (b & 1) {ans = ans * a ;}a = a * a ;b >>= 1;}return ans;}
ll fac[N];
void init(){
    fac[1]=1;
    for(int i=2;i<=N;++i){
        fac[i]=fac[i-1]*i;
    }
}
void solve() {
    int num,cnt,tmp=0,res=1;
    cin>>num;
    for(int i=2;i*i<=num;++i){
        if(!(num%i)){
            cnt=0;
            while(!(num%i)){
                num/=i;
                ++cnt;
            }
            tmp+=cnt;
            res*=fac[cnt];
        }
    }
    if(num>1){
        ++tmp;
    }
    int ans=fac[tmp]/res;
    cout<<tmp<<" "<<ans<<endl;="" }="" signed="" main()="" {="" tententen;="" int="" t="1;" cin="">> T;
    init();
    while (T--) {
        solve();
    }
    return 0;
}

标签：err,专题,const,cout,筛法,int,ll,牛客,define
From： https://www.cnblogs.com/tentenn/p/16874941.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99