Help needed MINIMUMOP Problem in START86

help
1

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?

2

The first version of your code doesn’t work correctly because you are changing a[i] during the innermost loop. Since you have set up f so that f[q] always contains a prime factor of q (unless q is 0 or 1), testing whether f[a[i]] divides a[i] will always succeed, unless a[i] is 0 or 1. So, the innermost loop, while(a[i]%f[a[i]]==0) a[i]/=f[a[i]];, will run until a[i] equals 1, at which point it will crash because you are attempting to take a remainder by f[a[i]], which is zero.

The second version of your code, as you give it above, fixes this problem, but it still doesn’t work correctly as it has a subtler problem. You fix the initially found prime factor of a[i] by storing it in x, and then test to see whether or not it is a factor of a[i], but the prime factor of a[i] which you divide by is not x but f[a[i]]. These will not always be the same. For example, if you start with a[i] equal to 18, x will be set to 3 and, after the division, a[i] will become 6, but now f[a[i]] is 2 and not 3. The result of this is that, after the next division, a[i] will become 3 and the prime factor 2 of the number you started with, 18, will not be recorded in the set st. For a case where this problem causes your revised program to give the wrong answer, you can take N=8 and M=19 and let A contain the elements 3, 5, 7, 11, 13, 17, 18, and 19. Your program will wrongly conclude that 2 divides no A_i and output a false one-operation solution, X=2.

If you take this second version of your code and change the division by f[a[i]] to be by x instead, then the factorization routine should function correctly.

3

Oh I got it… Thank you so much for the detailed reply :slight_smile: