暑假训练七

B. Turtle Fingers: Count the Values of k

题目要求

给定正整数 a, b, l，求有多少种 不同的非负整数 k 满足 l = k · a^x · b^y，其中 x, y ≥ 0。

思路

1. 枚举所有可能的 a^x 和 b^y

   • 外层循环：让 x = 0, 1, 2, ...，计算 a^x，一旦 a^x > l 立即停。

   • 内层循环：同理枚举 b^y。

2. 计算 k

   • 对每一对 (a^x, b^y)，只要 l % (a^x · b^y) == 0，则
         k = l / (a^x · b^y) 是一个合法解。

3. 去重

   • 用 unordered_set<int> 收集所有不同的 k，最后输出集合大小即可。

代码

#include<bits/stdc++.h>
using namespace std;
void solve(){
	long long a,b,l;
	cin>>a>>b>>l;
	unordered_set<int>res;
	long long k;
	long long x=1;
	while(x<=l){
		long long y=1;
		while(y<=l){
			long long r=x*y;
			if(l%r==0){
				k=l/r;
				res.insert(k);
			}
			y*=b;
            if(y>l)break;
		}
		x*=a;
		if(x>l)break;
	}
	cout<<res.size()<<endl;
}
int main(){
	int t;
	cin>>t;
	while(t--)solve();
	return 0;
}

E. Vasya and Multisets

题目要求

给定一个长度为 n（≤100）的正整数序列，把它 恰好分成两组（A 和 B），要求 两组中“好数”的个数相等。

• 好数定义：在 本组 里 恰好出现 1 次 的数。

• 如果无法做到，输出 NO；否则输出 YES 并给出任意一种分组方案（用字符串 A/B 表示）。

思路

先把全部数字扫一遍，统计每个数字的出现次数，并数出“好数”——也就是恰好出现一次的数字的个数。
如果这个好数个数是偶数，那就直接把每一个好数交替分到 A、B 两组里，其余数字全部塞进同一组；这样两组里的好数恰好各一半，答案输出 YES 并给出方案即可。
如果好数个数是奇数，就必须“借”一个出现次数大于等于 3 的数字来充当额外元素：把前一半好数分到 B，后一半好数分到 A，再把借来的那个数字的一个实例也分到 B，其余所有数字全部放A，这样两组里好数个数就平衡了，答案同样输出 YES 并给出方案。
如果连一个出现次数大于等于 3 的数字都没有，那奇数个好数无法平衡，只能输出 NO。

代码

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

/* 把数组大小开到 1000，足够容纳 1~100 的数值出现次数 */
const int maxn = 1000;
int d[maxn], vis[maxn];   // d[i] 存第 i 个元素；vis[x] 统计数字 x 的出现次数

int main()
{
    int flag = 0, tmp;        // flag 用来标记是否存在出现次数 ≥3 的数
                              // tmp 记录那个出现次数 ≥3 的具体数值

    int n, id = n - 1;        // n：元素个数；id 后面用来记录“最后一个出现次数为1的元素下标”
    cin >> n;                 // 读入 n
    for (int i = 0; i < n; i++)
    {
        cin >> d[i];          // 读入每个元素
        vis[d[i]]++;          // 统计每个数字出现次数
    }

    int ans = 0;              // ans 统计“出现次数恰好为 1”的数字个数（nice 数）
    for (int i = 1; i <= 100; i++)
    {
        if (vis[i] == 1)
            ans++;            // 每有一个 nice 数，ans+1
        if (vis[i] >= 3)
            flag = 1, tmp = i; // 发现出现次数 ≥3，记录到 flag 和 tmp
    }

    /* 找“最后一个”出现次数为 1 的元素下标，后面可能用它 */
    for (int i = 0; i < n; i++)
        if (vis[d[i]] == 1)
            id = i;

    /* 情况一：nice 数个数是偶数（ans & 1 == 0） */
    if (!(ans & 1))
    {
        cout << "YES" << endl;
        int g = 0;            // g 用来交替输出 A/B
        /* 把 nice 数依次交替分配到 A、B 两组，其余任意放 B */
        for (int i = 0; i < n; i++)
        {
            if (vis[d[i]] == 1 && g)
                cout << "A";
            else
                cout << "B";
            if (vis[d[i]] == 1)
                g ^= 1;       // 每出现一个 nice 数就切换一次
        }
        return 0;
    }

    /* 情况二：nice 数个数是奇数，且没有 ≥3 的数，无解 */
    if (flag == 0)
        return puts("NO"), 0;

    /* 情况三：nice 数个数是奇数，但存在 ≥3 的数，可以借一个“多余”的元素平衡 */
    cout << "YES" << endl;
    int cnt = 0, f = 0;       // cnt：已分配的前一半 nice 数；f：标记是否已经借用过 ≥3 的数
    for (int i = 0; i < n; i++)
    {
        if (cnt < ans / 2 && vis[d[i]] == 1)
        {
            cout << "B";      // 先放一半 nice 数到 B
            cnt++;
        }
        else if (vis[d[i]] >= 3 && f == 0)
        {
            cout << "B";      // 把 ≥3 的数借一个放到 B，充当“多余”元素
            f = 1;
        }
        else
            cout << "A";      // 其余全部放 A
    }
    cout << endl;

    return 0;
}

注意

• return 只能出现在 返回类型为 void 的函数里；

• main 的返回类型是 int，所以必须用 return 0;（或 return 任意整型值;），否则编译器报错。

因此，solve() 是 void，中间 return; 合法；
而 main() 是 int，中间或末尾必须写 return 0;。