ICPC-DHAKA-2019-PRELI/PROBLEM-G

Problem link : https://algo.codemarshal.org/contests/icpc-dhaka-19-preli/problems/G

#include<bits/stdc++.h>
#define ll  long long
#define dd long double
using namespace std;
ll status[10000004];
ll prime[10000004],sum[10000002],sum2[10000002];
ll p=0;

ll  phi[10000000];
void sivPhi()
{
    int x=10000000;
    for(int i=1;i<=x;i++)phi[i]=i;
    for(int i=2;i<=x;i++)
    {
        if(phi[i]==i)
        {
            phi[i]=i-1;
            for(int j=i*2;j<=x;j+=i)
                phi[j]=(phi[j]/i)*(i-1);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    sivPhi();
    ///siv();
    //for(ll i=1;i<=10000000;i++){sum[i]=go1(i);
    //sum2[i]=sum2[i-1]+sum[i];
    ///}
   /// cout<<"sum= "<<sum[6]<<endl;
    for(ll i=1;i<=10000000;i++)sum2[i]=sum2[i-1]+phi[i];
    int t;scanf("%d",&t);
    for(int a=1;a<=t;a++){
        ll x,y;

        scanf("%lld %lld",&x,&y);
        printf("Case %d: ",a);
        ll ans=lower_bound(sum2,sum2+10000001,y)-sum2;
        if(!sum2[ans] || !ans || sum2[ans]<y)printf("-1\n");
        else
        {
            ll bhag=(x/ans);
            if(bhag>x || bhag==0)printf("-1\n");
            else{
                printf("%lld\n",bhag);
            }
        }
    }
    //cout<<sum[1]<<endl;
    return 0;