题解：P11600 『Fwb』流星の陨落

WsW_ · 2025-01-21 23:23:24 · 题解

前言

把出题人 std 给爆了，请看帖子。
这种做法本质上是对出题人 std 的优化，具有可靠的时间复杂度。

思路

根据题意，我们可以认为 a_1=1。
令 b_i=a_i-a_{i-1}。题目就是要找到最大的 k，满足 k 是所有 b_i 的因子。
我们可以先求出 b_1 的因子有哪些，再枚举因子 k 并检查是否所有的 b_i 都能整除 k。找到最大的 k 即可。

假设找到一个因子 k，那么 A/k 一定也是因子，找因子只需要枚举到 \sqrt{A}。
查表可知，在 A\le 10^9 的时候 \max\{d(A)\}=1344。也就是说因子个数不超过 1344。
时间复杂度为 O\left(\sqrt{A}+d(A)\log d(A)+n\times d(A)\right)，比较极限。但常数极小，完全跑不满。

代码

#include<bits/stdc++.h>
using namespace std;
int n,ans;
vector<int>a;
vector<int>fac;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    a.push_back(1);
    while(n--){
        int x; cin>>x;
        if(x!=1)a.push_back(x);
    }
    int t=a[1]-a[0];
    for(int i=1;i*i<=t;i++){
        if(t%i==0){
            fac.push_back(i);
            fac.push_back(t/i);
        }
    }
    sort(fac.begin(),fac.end());
    for(auto x:fac){
        bool f=1;
        for(int i=1;i<a.size()&&f;i++){
            if((a[i]-a[i-1])%x)f=0;
        }
        if(f)ans=x;
    }
    cout<<(a.back()-1)/ans+1<<' '<<ans;
    return 0;
}