Codeforces Round #680 (Div. 2, based on Moscow Team Olympiad)

Powered by:AB_IN 局外人

A. Array Rearrangment

模拟即可。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e7+10;
int a[N],b[N];

int n,t,x;

int main()
{

    cin >> t;
    while(t--){
        cin >> n >>x;
        int f = 1;

        for(int i = 1 ;i <= n;i++) cin>>a[i];
        for(int i = 1 ;i <= n;i++) cin>>b[i];

        sort(a+1 , a+1+n);
        sort(b+1 , b+1+n, greater<int>());
        for(int i = 1 ;i <= n;i++) {
            if (a[i] + b[i] > x){
                f = 0;
                printf("No\n");
                break;
            }
        }
        if(f) printf("Yes\n");

        getchar();
    }
}
           

B. Elimination

随便蒙了几个关系就过了。。

题目没咋看懂。

for _ in range(int(input())):
    a , b , c , d = map(int , input().split())
    print(max( a + b , c + d))
           

C. Division

题意：求 p % x = 0 p \% x =0 p%x=0 x % q ≠ 0 x \% q \neq 0 x%q​=0 x x x的最大值。

分两种情况：

• p % q ≠ 0 p \% q \neq0 p%q​=0，那么 p p p就是那个最大的 x x x
• p % q = 0 p \% q =0 p%q=0， q q q的质因子一定包含在 p p p的质因子里面， x x x可以理解为 p p p除以任意个 p p p的质因子得到的数。那么问题就变得明朗许多。

先让 q q q素因子分解，这些素因子 p p p肯定包含，然后让 p p p一直除以某一素因子 s s s得到 x x x，直至 s s s在 p p p中的个数 小于 s s s在 q q q中的个数（可用 x % q ≠ 0 x \% q \neq 0 x%q​=0保证），这样得出的 x x x一定无法整除 q q q，每次对 x x x取个最大值即可。

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll p, q;
int t;
int main()
{
    cin >> t;
    while( t -- )
    {
        cin >> p >> q;
        vector < int > v;
        if(p % q != 0) cout << p <<endl;
        else{
            ll tmp_q = q;
            ll tmp_p = p;
            for(int i = 2;i <= tmp_q / i; i++)
            {
                while(tmp_q % i==0){
                    tmp_q /= i;
                    v.push_back(i);
                }
            }
            if(tmp_q > 1) v.push_back(tmp_q);
            ll mx = -1;
            for(int i = 0; i < v.size(); i++){
                tmp_p = p;
                while(tmp_p % q == 0)
                {
                    tmp_p /= v[i];
                }
                mx = max(tmp_p , mx);
            }
            cout << mx <<endl;
        }
    }
    return 0;
}

           

对 a a a的素因子分解

vector < int > v;
for(int i = 2;i <= a / i; i++){
    while(a % i==0){
        a /= i;
        v.push_back(i);
    }
}
if(a > 1) v.push_back(a);
           

完结。