Codeforces Round #729 (Div. 2) A,B,C

A. Odd Set

题意：2n个数问能不能奇偶配对

题解：签到题，只要当奇数的个数和偶数的个数相同时才可以凑数n对

解题代码：

#include <bits/stdc++.h>
using namespace std;
signed main(){
	fio;
	int t;
	cin >> t;
	while(t--){
		int n,tmp;
		cin >> n;
		int od = 0,eve = 0;
		for(int i = 1;i<= 2 * n;i++){
			cin >> tmp;
			if(tmp % 2)od++;
			else eve++;
		}
		if(od == eve)cout << "Yes\n";
		else cout << "No\n";
	}
} 

B. Plus and Multiply

题意：给一个集合，初始集合中只有一个1，可以将x进行x*a或者x+b问n在不在这个集合中

题解：容易想到有两种情况下是正确方案，一种是（x - 1）% b == 0 的时候，另外一种是x为a的幂的时候。所以我们构造一个数y使得y % b == x % b，之后就是构造过程了，1得到y，y的余数则会变成x的余数乘a；对x进行操作2余数不改变。而开始我们只有一个数1，要让1的余数改变成我们需要的x，我们需要对它进行若干次操作1，直到x大于n，或者y % b == x % b。

解题代码：

#include <iostream>
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
signed main() {
	fio;
    int t;
    cin >> t;
    while (t--) {
        int a, b, n;
        cin >> n >> a >> b;
        bool f  = false;
        for (int  x = 1; x <= n; x *= a) {
            if ((n - x) % b == 0) {
                f = true;
            }
            if (a == 1) {
                break;
            }
        }
        if (f)cout << "Yes\n";
		else cout << "No\n";
    }
    return 0;
}

C. Strange Function

题意：对一个数，能找到他的最非小因子，1是2,2是3,3是2,4是3,5是2...，现在要求1到这个数的所有最小非因子的和

解题思路：

对于这个非因子的和，如果新加入的数已经被包含在前面所有数的最小公倍数中，那么这个数要跳过，否则会剩下该数与之前最小公倍数的最小公倍数除以之前的最小公倍数分之一个数，向下取整，耗费为当前的数字乘以减去的数字

解题代码：

#include <iostream>
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int mod = 1e9 + 7;
signed main(){
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		int idx = 2;
		int pre = 1;
		int nx = 2;
		int ans = 0;
		while(n){
			if(nx != pre){
				int takn = nx / pre;
				int tn = n / takn; 
				ans += idx * (n - tn);
				ans %= mod;
				n = tn;		
			}
			idx++;
			pre = nx;
			nx = nx * idx / __gcd(nx,idx);
		}
		cout << ans << endl; 
	}
}