【每日一题】—— D. Divide and Equalize（Codeforces Round 903 (Div. 3)）（数学、数论）

本文主要是介绍【每日一题】—— D. Divide and Equalize（Codeforces Round 903 (Div. 3)）（数学、数论），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

🌏博客主页：PH_modest的博客主页
🚩当前专栏：每日一题
💌其他专栏：
🔴 每日反刍
🟡 C++跬步积累
🟢 C语言跬步积累
🌈座右铭：广积粮，缓称王！

一.题目描述

在这里插入图片描述

题目大意：

给你一个由 $n$ 个正整数组成的数组 $a$ 。你可以对它进行以下操作：

选择一对元素 $a_i$ 和 $a_j$ （ $\le i, j \le n$ 和 $\neq j$ ）；
选择整数 $a_i$ 的除数之一，即整数 $x$ ，使得 $a_i \bmod x = 0$ ；
用 $\frac{a_i}{x}$ 代替 $a_i$ ，用 $a_j \cdot x$ 代替 $a_j$ 。
判断是否有可能通过一定次数（可能为零）的运算使数组中的所有元素都相同。
例如，数组 $a$ = [ $100, 2, 50, 10, 1$ /]包含 $5$ 个元素。对它进行两次运算：
选择 $a_3 = 50$ 和 $a_2 = 2$ , $x = 5$ .用 $\frac{a_3}{x} = \frac{50}{5} = 10$ 替换 $a_3$ ，用 $a_2 \cdot x = 2 \cdot 5 = 10$ 替换 $a_2$ 。得到的数组是 $a$ = [ $100, 10, 10, 10, 1$ ]；
选择 $a_1 = 100$ 和 $a_5 = 1$ , $x = 10$ .用 $\frac{a_1}{x} = \frac{100}{10} = 10$ 替换 $a_1$ ，用 $a_5 \cdot x = 1 \cdot 10 = 10$ 替换 $a_5$ 。得到的数组是 $a$ = [ $10, 10, 10, 10, 10$ ]。
进行这些运算之后，数组 $a$ 中的所有元素都等于 $10$ 。

题目链接：

D. Divide and Equalize（Codeforces Round 903 (Div. 3)）

二.思路分析

题目的意思就是将一个数的因子给另一个数，使得最后数字要相同
也就是说最后每个数的因子都是一样的
所以只需要分解每个数，最后判断一下每个因子的个数是不是n的倍数就可以了

三.代码展示

//https://codeforces.com/contest/1881/problem/D
//分解所有的数，如果最后所有因子都是n的倍数，那就是yes
//
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
#define int long long
using namespace std;void solve()
{map<int,int>mp;int n;cin>>n;for(int i=0;i<n;i++){int a;cin>>a;for(int j=2;j*j<=a;j++){while(a%j==0){mp[j]++;a/=j;}}mp[a]++;}for(auto x:mp){if(x.first<=1){continue;}if(x.second%n!=0){cout<<"NO"<<"\n";return;}}cout<<"Yes"<<"\n";
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}