Codeforces Round 889 (Div. 2) B. Longest Divisors Interval
题目链接:题目
大意:
给定一个数n,找出一个最长区间使得这个区间内都是n的因数,输出长度。
思路:
如果要找的区间存在于1-n某个未知的位置,那么几乎没有足够快的算法。但是有一个结论: [ 1 , l − r + 1 ] [1,l -r+1] [1,l−r+1]的所有数一定有倍数位于 [ l , r ] [l,r] [l,r]区间,这是因为一个数的倍数的出现是有周期的,那么如果一个区间大于这个周期,那么一定存在一个倍数。
代码:
#include <bits/stdc++.h>
using namespace std;#define int long long
#define MOD 1000000007
#define fi first
#define se second
#define pii pair<int,int>
#define vec vectorvoid solve(){int n;cin >> n;for(int i = 1; i <= n; i++){if(n % i != 0){cout << i - 1 << '\n';return;}}cout << n << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin >> t;while(t--){solve();}return 0;
}