题解：P10337 [UESTCPC 2024] 操作序列

· · 题解

前言

这题代码操作并不难，但思维难度是有的，连我也去评论区看了看别人的思路才做出来的。

解题思路

首先，我们可以先证明一个很重要的结论：

假设有一个序列 a：

2,3,4,5

我们把除了 a_1 以外的所有数都乘 2：

2,6,8,10

我们再拿原来的 a，把这里 a_1 除以 2：

1,3,4,5

我们会发现，虽然值不同，但是每个数之间的倍数关系是不变的！这就跟老师给全班同学发了了一台电脑（怎么可能），唯独你没有被发到。这个例子和老师到你家去抢了一台电脑一样，每名同学间电脑的数量差一样的（其实就是等式的性质，只不过有多个数）。

所以说，把一个长度为 n 的序列中 n-1 个数的值乘一个相同的数，等于拿剩下的那个数除以这个相同的数。

我们不难想到，当所有 a_i 的值相同时，我们可以把 n 个数都乘一遍，而且只用操作一次。

而 a_i 的值并不完全相同时，我们进行 n-1 次操作，每次操作把第 i 个数 a_i 除以它自己，就可以最后变成一个每项都为 1 的序列了。

结论：a_i 相同时，答案为 n ，否则为 n-1。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define I return
#define love 0
#define FIRESTARS ;
int a[10005];
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t,n,f=1;cin>>t;
    while(t--)
    {
        f=1;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=2;i<=n;i++)
        if(a[i]!=a[i-1])
        {
            f=0;
            break;
        }
        cout<<(f?n:n-1)<<'\n';
    }
    I love FIRESTARS
}