D. Magic LCM
\(1.当我们在模拟样例1时，我们发现当最后为1，2， 2， 10 ，20时和最大\)
\(模拟样例3时，我们发现当最后为，1，1，6，6，36，540时和是最大\)
\(样例2无需修改加起来就是最大的。\)
\(2.我们发现，最后的序列每一个数都是后面的质因子，那么本质上，求最大的和，就是\)
\(移动这些质因子幂数(比如2^2,3^2)到其他数相乘，而一个质因子幂数可以移动到另一个数\)
\(的条件是，它们之间有不同的质因子。\)
\(3.我们使用一个二维数组，每行存的是对应质因子的幂数，那么不同行的相同位置，其实\)
\(就\color{red}{确保了，有不同质因子的这个条件}，\)\(举个例子：样例3\)
\(4.那么对应的位置相乘起来，便是每个数的最优贡献。但是还要注意，假如6个数，质因子对应的幂数最多有4个，那么剩余两个数最后就是1。\)
总结：对这个几个数分解质因数--->存入对应的质因数的幂数--->排序后对应位置相乘--->加上剩余的1--->过程和结果的取模
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define ull unsigned long long
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
#define mod 998244353
int n;
bool vis[1010];
vector<int>pri;//放1000以内的质数，大于1000的质数直接加到结果就行，因为最大数1e6。
void olas()//线性筛素数法
{
for(int i=2;i<=1005;i++)
{
if(!vis[i]) pri.push_back(i);
for(auto v:pri)
{
if(i*v>1005) break;
vis[i*v]=1;
if(i%v==0) break;
}
}
}
vector<int>v[1000010];//存每种质数对应的数比如质因数2 存4 8 16 质因数3存3 9 27
set<int>se;//存共出现了多少种质数，方便后续的遍历
void get(int x)//用来把每个数分解
{
for(auto t:pri)
{
if(x<t) break;
if(x%t==0) {
int temp=1;
while(x%t==0){
temp*=t;
x/=t;
}
v[t].push_back(temp);//存质因子对应次幂的数
se.insert(t);
}
}
//大于1000的质数直接放进来就可以
if(x>1){
v[x].push_back(x);
se.insert(x);
}
}
void solve()
{
cin>>n;
for(int i=0;i<n;i++)
{
int x; cin>>x;
get(x);
}
int maxx=0,mk=0;//maxx是存质因数对应数数组里的最大长度，mk标记最大长度质因数
for(auto i:se){//寻找maxx与mk
if((int)v[i].size()>maxx) maxx=v[i].size(),mk=i;
sort(v[i].begin(),v[i].end(),greater<int>());//从大到小排序
}
for(auto i:se)
{
if(i==mk) continue;//把其他可以加的质因数幂次数加到这个数组里，所以这个数组不操作
for(int j=0;j<v[i].size();j++)
{
v[mk][j]=v[mk][j]*v[i][j]%mod;//对应位置相乘比如27 9 3 3
} // 和4 2 4 4
}
int ans=n-maxx;//质数因子移动的过程结束后，n-maxx个数是1
for(auto t:v[mk]) ans=(ans+t)%mod;//这里不是+= 是=
for(auto t:se) v[t].clear();
se.clear();
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0);
int t=1; cin>>t;
olas();
while(t--)
{
solve();
}
}
C. Liar
最多可以有n-1个人说的是实话，因为1个说假话的人的这个数据可能可以直接弥补n-1个人和s的差值
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define ull unsigned long long
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
#define mod 998244353
signed main()
{
int n,s; cin>>n>>s;
int sum=0;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
sum+=x;
}
if(sum==s) cout<<n;
else cout<<n-1;
}
G. Multiples of 5
一个数是不是5的倍数，只取决于最后一位，11的任意次方的最后一位为1，每个进制位上的数字，实际上代表的是最后一位有多少个1，那么只需要计算出所有位置上加起来的数字和是不是5的倍数即可，注意A代表的是10
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define ull unsigned long long
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
#define mod 998244353
void solve()
{
int n; cin>>n;
int sum=0;
for(int i=0;i<n;i++)
{
int a;
string b;
cin>>a>>b;
int a1,b1;
if(b=="A") b1=10;
else b1=stoi(b);
sum+=a*b1;
}
if(sum%5==0) cout<<"Yes";
else cout<<"No";
cout<<endl;
}
signed main()
{
int t=1; cin>>t;
while(t--)
{
solve();
}
}
Magic Mahjong
1.十三orphans就是：取满对应的13个，剩余一个也来自这十三种的一种，那么使用map标记，大小对应13，并且有一个元素的数量是2即可
2.七对就是：对应的种类中，每种取2张，取7种即可
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define ull unsigned long long
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
#define mod 998244353
void solve()
{
map<string,int>fi;
vector<string>v={"1z","2z","3z","4z","5z","6z","7z",
"1p","9p","1s","9s","1m","9m"
};
for(auto t:v){
fi[t]=1;
}
vector<string>ve;
string s; cin>>s;
for(int i=0;i<s.size();i+=2)
{
string sb;
sb+=s[i];
sb+=s[i+1];
ve.push_back(sb);
}
map<string,int>mp;
for(auto t:ve) mp[t]++;
int flag=0;
if(mp.size()==13){
for(auto t:mp){
if(fi[t.x]==0){
cout<<"Otherwise";
flag=1;
break;
}
}
if(!flag) cout<<"Thirteen Orphans";
}else
if(mp.size()==7)
{
for(auto t:mp){
if(t.y!=2){
cout<<"Otherwise";
return ;
}
}
cout<<"7 Pairs";
}
else cout<<"Otherwise";
cout<<endl;
}
signed main()
{
int t=1; cin>>t;
while(t--)
{
solve();
}
}