邪恶音级
在每一轮筛选中,保留的元素下标均为k的倍数,导致剩余元素在原数组中的位置逐步成为k的幂次方。最终,最大的k的幂次方成为唯一无法被后续操作淘汰的数。所以就可以将这题转化为寻找一个最大的n,满足 kⁿ <= l。由于最高次幂可能存在多个及kⁿ,2kⁿ……,(n-1)kⁿ 导致可能存在多个解,此时分为两种情况 :
情况一 : K % 7 == 0 ,那么任意筛选一次即可使得所有筛选得到的数字 % 7 == 0 , 答案也唯一确定了就是 "si" ;
情况二 : K % 7 != 0 ,由于 7 是一个质数 且 K % 7 != 0 所以 k 的任意正整数次方都不能整除 7 。单看系数 1 和 2 就能知道 ,这数组里的所有数 % 7 的余数永远不可能相等 , 只有一种情况例外,最后一轮恰好只剩下一个数 。
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll l, n, k; string music[7] = {"si", "do", "re", "mi", "fa", "so", "la"}; int main() { cin >> n; while(n--){ cin >> l >> k; ll sum = k; while(sum <= l / k && k != 1){ sum *= k ; } if (k % 7 != 0){ if (l / sum == 1) cout << music[sum % 7] << endl; else cout << -1 << endl; }else cout << "si" << endl; } return 0; }