暑假训练七
B. Turtle Fingers: Count the Values of k
题目要求
给定正整数 a, b, l，求有多少种 不同的非负整数 k 满足 l = k · a^x · b^y，其中 x, y ≥ 0。
思路
枚举所有可能的 a^x 和 b^y
外层循环：让
x = 0, 1, 2, ...，计算a^x，一旦a^x > l立即停。内层循环：同理枚举
b^y。
计算 k
对每一对
(a^x, b^y)，只要l % (a^x · b^y) == 0，则k = l / (a^x · b^y)是一个合法解。
去重
用
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; // 读入 nfor (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+1if (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";elsecout << "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 数到 Bcnt++;}else if (vis[d[i]] >= 3 && f == 0){cout << "B"; // 把 ≥3 的数借一个放到 B，充当“多余”元素f = 1;}elsecout << "A"; // 其余全部放 A}cout << endl;return 0;
}注意
return只能出现在 返回类型为void的函数里；main的返回类型是int，所以必须用return 0;（或return 任意整型值;），否则编译器报错。
因此，solve() 是 void，中间 return; 合法；
而 main() 是 int，中间或末尾必须写 return 0;。