A. Di-visible Confusion

A. Di-visible Confusion

// Problem: A. Di-visible Confusion// Contest: Codeforces - Codeforces Round #752 (Div. 1)// URL: Memory Limit: 256 MB// Time Limit: 1000 ms// 2022-02-18 14:58:38// // Powered by CP Editor (namespace std;#define rep(i,l,r) for(int i=(l);i<=(r);i++)#define per(i,l,r) for(int i=(l);i>=(r);i--)#define ll long long#define pii pair#define mset(s,t) memset(s,t,sizeof(t))#define mcpy(s,t) memcpy(s,t,sizeof(t))#define fir first#define pb push_back#define sec second#define sortall(x) sort((x).begin(),(x).end())inline int read () { int x = 0, f = 0; char ch = getchar(); while (!isdigit(ch)) f |= (ch=='-'),ch= getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return f?-x:x;}template void print(T x) { if (x < 0) putchar('-'), x = -x; if (x >= 10) print(x/10); putchar(x % 10 + '0');}const int N = 1e5 + 10;int a[N];int n;vector te;ll gcd (ll a, ll b) { return b?gcd(b, a %b) : a;}ll lcm (ll a, ll b) { return a * b / gcd (a, b);}void solve() { te.clear(); cin >> n; ll temp = 2; bool f = 1; for (int i = 1; i <= n; i++) { cin >> a[i]; if (i <= 22) temp = lcm(temp, i+ 1); if (a[i] % temp == 0) { f = 0; } } if (f) puts("Yes"); else puts("No"); }int main () { int t; cin >> t; while (t --) solve(); return 0;}

结论: 如果能全部消除，当且仅当对于每一个i对存在2,~i不能够整除a[i] 对于一个序列 假设前缀1~n - 1能够被消除。对于a[n]如果存在一个位置k，能够消除，那么a[n]也能被消除. 如果a[i]能够被2~i整除，那么lcm(2, ... i)也能够整除a[i]，又由于lcm(2, 23)大于1e9所以只需要检查小于23就行了。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。