In todays START86, I saw something very weird. My code for MINIMUMOP was:
#include<bits/stdc++.h>
using namespace std;
#define fo(i,n) for(i=0;i<n;i++)
#define fop(i,x,n) for(i=x;i<=n;i++)
#define forv(i,l,n) for(i=l;i>=n;i--)
#define uniq(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) x.begin(),x.end()
#define ll long long
#define mod 1000000007
#define pb push_back
#define print(x) for(auto it:x) cout<<it<<' ';cout<<nl
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<string> vs;
ll N=1e6+2;
vb sp(N,true);
vl p,f(N);
void sieve(){
ll i,j;
sp[0]=sp[1]=false;
fop(i,2,N-1){
if(sp[i]){
f[i]=i;
for(j=i*i;j<N;j+=i) sp[j]=false,f[j]=i;
}
}
fop(i,2,N-1) if(sp[i]) p.pb(i);
}
void solve(){
ll n,m,i;
cin>>n>>m;
vl a(n);
set<ll> st;
fo(i,n) cin>>a[i];
if(count(all(a),a[0])==n){
cout<<"0\n";
return;
}
ll g=a[0];
fop(i,1,n-1) g=__gcd(g,a[i]);
if(g>1){
cout<<"1\n"<<g<<"\n";
return;
}
fo(i,n){
while(a[i]>1){
st.insert(f[a[i]]);
while(a[i]%f[a[i]]==0) a[i]/=f[a[i]];
}
}
i=upper_bound(all(p),m)-p.begin()-1;
while(1){
if(st.find(p[i])==st.end()){
cout<<"1\n"<<p[i]<<'\n';
return;
}
i--;
if(i<0) break;
}
cout<<"2\n2 3\n";
}
int main(){
fastio
int t=1;
cin>>t;
sieve();
while(t--) solve();
return 0;
}
I got RE repeatedly (SIGFPE) for the rest of the contest.
In the part
fo(i,n){
while(a[i]>1){
st.insert(f[a[i]]);
while(a[i]%f[a[i]]==0) a[i]/=f[a[i]];
}
}
When I was debugging after the contest (honestly, just performing random changes), I found that storing f[a[i]] in some variable and then performing modulo gave AC.
fo(i,n){
while(a[i]>1){
ll x=f[a[i]];
st.insert(f[a[i]]);
while(a[i]%x==0) a[i]/=f[a[i]];
}
}
I am not able to understand why. Would someone pls help?