yzoj 2372 小B的數字 題解

題意

判斷是否存在一個序列 $ b_i $ 使得 $ \prod_{i = 1}^{n} b_i  | b_i^{a_i}$ 恆成立，其中 $ b_i $ 中的每個數都是2的正整數次冪。

樣例輸入

3
2
3 2
3
3 3 3
2
1 10

樣例輸出

YES
YES
NO

數據範圍

對於 100% 的數據有 $ n \leq 10^5,a_i \leq 10,T \leq 10$

解析

首先拿到這道題，考場一看就知道不是規律題就是數學公式題，事實上是的。

我們可以設 $ b_i=2^{x_i} $ 其中 $ x_i \(為正整數，\) lcm(a_1,a_2,a_3....a_n)=LCM $ , $ sum=\sum_{i = 0}^{n} x_i $。

那麼我們可以將原式子化為 $ 2^{sum} | 2^{x_i * a_i} $,顯然要使此式恆成立，就要滿足 $ a_i * x_i \geq sum $.

此式子可以轉化為 $ lcm* x_i \geq sum* \frac{lcm}{a_i} $

左右兩邊相加可得

$ lcm* sum \geq sum * ( \sum_{i = 1}^{n} {\frac{lcm}{a_i}} )$

即 $ lcm \geq ( \sum_{i = 1}^{n} {\frac{lcm}{a_i}} )$

兩邊提出 $ lcm $約去得到 $ 1 \geq ( \sum_{i = 1}^{n} {\frac{1}{a_i}} )$

那麼我們可以得出最終公式就是 $ ( \sum_{i = 1}^{n} {\frac{1}{a_i}} \leq 1) $

如果我們直接同分比較，很顯然會超數據範圍。

對於這一題，由於涉及倒數，會產生浮點誤差，我們有三種方法去處理

方法一（不推薦

在最終判斷的時候設置精度進行調控

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-6;
int T,n,k;
bool cheak(double a,double b){
    if(a-b<=eps) return true;
    else return false;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        double sum=0;
        for(int i=1;i<=n;++i){
            scanf("%d",&k);
            sum+=1.0/(double)k;
        }
        if(cheak(sum,(double)1)) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

方法二(正解

我們可以觀察數據，可以知道 $ a_i \leq 10 $ 我們最終得到得式子也只與 $ a_i $ 得倒數有關,所以我們可以將式子改造，左右兩邊乘以 $ 10! $,也就是
$ ( \sum_{i = 1}^{n} {\frac{10!}{a_i}} \leq 10!) $

於是運算便變為了整數運算，便不存在浮點誤差了！（常用技巧）

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std; 
typedef long long ll;
int main(){ 
   int t; 
   scanf("%d",&t); 
   while (t--){
       int n; 
       scanf("%d",&n); 
       ll tot=0; 
       for(int i=0;i<n;i++){
           int x;
           scanf("%d",&x); 
           tot+=3628800/x; 
       }
       puts(tot<=3628800 ? "YES" : "NO");
   }
   return 0; 
}

方法三(巧妙的暴力

分析式子 $ ( \sum_{i = 1}^{n} {\frac{1}{a_i}} \leq 1) $ 我們可以發現如果 $ n > max(a_i) $ 那麼這個式子必然不成立，所以我們可以把n的範圍縮小到 $ max(a_i) $ 以內，那麼我們通分就不會超出範圍了於是便有了一個愉快的暴力

#include<bits/stdc++.h>
using namespace std; 
int main(){ 
    int t; 
    scanf("%d",&t); 
    while (t--){
        int n;bool flag=1; 
        scanf("%d",&n); 
        long long tot=0;
        long long pop=1; 
        int maxn=0; 
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x); 
            maxn=max(maxn,x);
            if(x==1) flag=0;
            tot+=x;
            pop*=x;
        }
        if(!flag || n>maxn) printf("NO\n");
        else puts(tot<=pop ? "YES" : "NO");
    }
    return 0; 
}