DIVREC Editorial

PROBLEM LINK:

https://www.codechef.com/START24C/problems/DIVREC

Setter: Harsh Vardhan Goenka
Tester: Aryan Chaudhary
Editorialist: Rishabh Gupta

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

Alice is teaching Bob maths via a game called N-guesser.

Alice has a number N which Bob needs to guess.

Alice gives Bob a number X which represents the sum of divisors of N. Alice further provides Bob with A and B where A/B represents the sum of reciprocals of divisors of N.

Bob either needs to guess number N or tell that no such number exists.

EXPLANATION:

The divisors of a number n are of the form a_1, n/a_1, a_2, n/a_2, a_3, n/a_3 …sqrt(n) (only if it divides n). So, the sum of reciprocal of the divisors of a number is nothing but the sum of divisors of the number divided by the number n itself.
So, we can the get the number n as X*B/A. But, we have to check that this n yields the same sum of the divisors as given input X, which will require O(sqrt(n)) time.

TIME COMPLEXITY:

O(sqrt(n)) for each test case.

SOLUTION:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long t;
    cin>>t;
    while(t--){
        long long n,x,a,b;
        cin>>x>>a>>b;
        long long c=gcd(a,b);
        while(c!=1){
            c=c;
        }
        n=(x*b);
        if(n%a!=0){
            cout<<"-1\n";
            continue;
        }
        n/=a;
        if(n>1e9){
            cout<<"-1\n";
            continue;
        }
        long long sum=0ll;
        for(long long i=1;i*i<=n;i++){
            if(n%i==0){
                sum+=i;
                if(i!=n/i)
                    sum+=n/i;
            }
        }
        if(sum==x)
            cout<<n<<"\n";
        else
            cout<<"-1\n";
    }
}
Editorialist''s Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
#define endl "\n"
#define pb push_back
#define all(v) v.begin(),v.end()
#define mp make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pll pair<ll,ll>
#define fo(i,n) for(int i=0;i<n;i++)
#define fo1(i,n) for(int i=1;i<=n;i++)
ll mod=1000000007;
ll n,k,t,m,q,flag=0;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds; 
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(a) -- no. of elements strictly less than a
// s.find_by_order(i) -- itertor to ith element (0 indexed)
ll min(ll a,ll b){if(a>b)return b;else return a;}
ll max(ll a,ll b){if(a>b)return a;else return b;}
ll gcd(ll a , ll b){ if(b > a) return gcd(b , a) ; if(b == 0) return a ; return gcd(b , a%b) ;}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifdef NOOBxCODER
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #else 
    #define NOOBxCODER 0
    #endif
    cin>>t;
    //t=1;
    while(t--){
        ll a,b,c;
        cin>>a>>b>>c;

        if(a%b !=0 || c>b){cout<<-1<<endl; continue;}
        c *= a/b;

        ll sum=0;
        for(int i=1;i*i<=c; i++){
            if(c%i!=0)continue;
            if(i*i==c)sum+=i;
            else sum+= i + c/i;
        }
        if(sum == a)cout<<c<<endl;
        else cout<<-1<<endl;





        
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}

3 Likes

Can someone please tell my why this code gave me TLE? I mean, come on… it has same logic.

Link

@admin Please reply.

5 Likes

@admin Many solutions submitted will give 2 as answer for X=4, A=2, B=1, when -1 is the correct answer. Are the testcases weak, or am I missing something?

1 Like

+1 My Submission

I used prime sieve to find the primes and then calculated the sum using prime and its exponents. Though both are sqrt(n) but I think this approach has lower constant than iterating on all numbers till sqrt(n)
My submission Solution: 57628069 | CodeChef

@admin Very weak test cases, a lot of participants just submitted without even checking the sum of divisors.

For test case

x = 4 , a = 2, b =1 according to many passed solutions :- ans = 2

but there exist no answer for this case.

https://www.codechef.com/viewsolution/57638044

This is a sample solution which passed all the test cases. Here, without checking whether

sum of divisor they claimed that answer exist. Which is quite wrong.

Because of these poor test cases the question got very high submissions. Please look into this, my rank got very worsened because of this.

12 Likes

How can you say if N > 1e9, answer is no.
you never specified the we cannot number greater than 1e9 . rest all, I also did the same, but my solution
got TLE. Because of this 1e9 case but this is not the right way you can say that N > 1e9 No solution exist.

2 Likes

Why do we need to check that the sum of divisors =x ??? Why does X*B/A does not guarantee the answer ?? Can someone prove it mathematically ??

@ayush29azad if a number with given x,a,b exists, it’s unique… But it is not necessary that it will exist… For example x,a,b=8,4,3, doesn’t have a solution but using formula u get, 6 as result which is wrong.

Unfortunately, the test cases are too weak to detect this.

2 Likes

If you would have checked if ( a< b) then clearly said -1. Then it wouldn’t cost you TLE

See suppose we are doing it for n = 4. X = 7 and A/B = 7/4 right. But notice that
X = 8 , A = 8 , B = 4 also gives answer 4. Infact anything of the form (X,A,B) = (k,k,4) would give answer 4 only. But we know that unique answer is k = 7. Thus we need to check the sum also.

2 Likes

my code, I just forgot to write the condition of 1 and got unnecessary WA :frowning:

1 Like

I did this problem in O(1).

Same here wasted 25 mins due to that silly TLE

there may be case where A is one and X is large number , so we are going to traverse B unnecessarily, so in starting we can check that A>B.

not exactly anything of the form k, k, 4… considering gcd(a, b) = 1… but yeah, u r right… checking sum is actually necessary over so many test cases…

yepp, that is actually necessary…

For me replacing cin/cout with scanf/printf worked!

1 Like

The input you are giving is wrong. A=2 and B=1 mean sum of reciprocals would be 2/1= 2. But that is not possible, sum of reciprocals would always be less than 1.
In other words, A will always be less than B.

dont use int_32
modification of your solution