GUESSNUM Editorial

PROBLEM LINK:

Practice
Contest

Tester: Roman Bilyi
Editorialist: Hussain Kara Fallah

PROBLEM EXPLANATION

Chef is playing a game with his brother Chefu. He asked Chefu to choose a positive integer N, multiply it by a given integer A, then choose a divisor of N (possibly N itself) and add it to the product. Let’s denote the resulting integer by M; more formally, M=A⋅N+d, where d is some divisor of N.

Chefu told Chef the value of M and now, Chef should guess N. Help him find all values of N which Chefu could have chosen.

DIFFICULTY:

Easy

CONSTRAINTS

1 \leq M \leq 10^{10}

EXPLANATION:

Initially, we know that:
M=A*N+D
But D is a divisor of N so N=Q*D So:
M=A*Q*D+D
M=D*(A*Q+1)
So we know that D must be a divisor of M also.
Let’s check all divisors of M, this can be done in O(\sqrt{N}) complexity
For each divisor d let’s find R=\frac{M}{d}-1
Now if R is divisible by A then we have q=\frac{R}{A} and we have a potential candidate of N which is q*d. After finding all candidates just sort them and remove duplicates and output the values. Also, just make sure you don’t consider 0 as a possible answer.

Editorialist solution
#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;
    while (T--) {
        long long A, M;
        cin >> A >> M;
        set<long long> ans, div;
        for (long long j = 1; j * j <= M; j++) {
            if (M % j == 0) {
                div.insert(j);
                div.insert(M / j);
            }
        }
        for (auto D : div   ) {
            long long q, rem = M / D;
            rem--;
            if (rem % A) continue;
            q = rem / A;
            ans.insert(q * D);
        }
        ans.erase(0);
        cout<<ans.size()<<endl;
        for(auto pp : ans)
            cout<<pp<<' ';
        cout<<endl;
    }


}
Tester Solution
	#include "bits/stdc++.h"
#include <chrono>
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long Int;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000;
const Int LINF = INF * (Int) INF;
const int MAX = 200007;

const int MOD = 1000000007;

const double Pi = acos(-1.0);

long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);

			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			assert(cnt>0);
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
void eof() {
	string trash;
	assert(!(cin >> trash));
}

Int F(Int M, Int A, Int d)
{
	if (d >= M) return -1;
	M -= d;
	if (M % A != 0) return -1;
	M /= A;
	if (M % d != 0) return -1;
	return M;
}

int main(int argc, char* argv[])
{
	ios::sync_with_stdio(false); cin.tie(0);
	srand(time(0));

	int t = readIntLn(1, 100);
	FOR(tt,0,t)
	{
		int A = readIntSp(1, 1000000);
		Int M = readIntLn(1, 10000000000LL);
		assert(A < M);
		vector<Int> res;
		for(Int i = 1; i * i <= M; i++)
			if (M % i == 0)
			{
				Int x = F(M, A, i);
				Int y = F(M, A, M / i);
				if (x != -1)
					res.push_back(x);
				if (y != x && y != -1)
					res.push_back(y);
			}
		sort(ALL(res));
		cout << SZ(res) << endl;
		FOR(i,0,SZ(res))
		{
			cout << res[i] << ' ';
		}
		cout << endl;
	}	

	eof();

	cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
} 
4 Likes

What is this statement for?

1 Like

https://www.codechef.com/viewsolution/28592030
Can any one help me understand why I am getting RE (NZEC) for this solution?

even with this its not passing original constraints !!?.. what to do !?
PS: i used the same approach and code is almost similar too as that of editorialist

The “almost” similar code has a bug then.

2 Likes

https://www.codechef.com/viewsolution/28585953
plz help in finding bug in my code

Sorry, I don’t know JAVA that well, I code in C++

long a = s.nextInt();
long m = s.nextInt();

m <= 10^10 and a<m
use s.nextLong() instead

Use long for storing A and M

We are storing all the factors of M in set div. If j is a factor of M that means M/j is a factor too. Hence, inserting both j and M/j in div.

@ankit_2305 its still not passing original constraints :disappointed_relieved:

                for (long f : arrLL){ 
		        if ((f-1)%a == 0){
		            long q = (f-1)/(int)a;
		            **long d = (int)m/f;**
		            long n = q*d;
		        if (n != 0 ){
		        newarrLL.add(n);
		        count ++;
		        }
		        }
		    }

@raksha1906
It is a similar mistake, typecasting long m to int will alter the value of m for values lying outside the range of integer which will result in unexpected output.
You may replace
long d = (int)m/f;
with
long d = m/f;

1 Like

it got solved … thanks

while (t–>0) {

		long a = s.nextLong();
		long m = s.nextLong();
		ArrayList<Long>mr= new ArrayList<>();
		long k =(long) Math.floor(Math.sqrt(m));
		for (int j = 1; j <=k; j++) {
            if (m%j==0){
                long r = m/j;
                if ((j-1)%a==0){
                    mr.add(((j-1)/a)*r);
                }
                if(	r!=j){                  // THIS BLOCK
                    if ((r-1)%a==0){
                        mr.add(((r-1)/a)*j);
                    }
                }
            }
        }
		System.out.println(mr);
		
	}

hey can you also explain me what the second if block is doing ?

this is for …
since q = (j-1)/a … and q is an integer, so j-1 should be completely divisible a…
so (j-1)%a == 0 helpes in checking whether this condition is satisfied or not … and only accepts those values of q which satisfies the condition

yes that’s the first if block what about this one ?? i wasn’t able to come up with this condition

My solution is little bit different .it is able to pass 50 % but next its showing TLE. can anyone please help https://www.codechef.com/viewsolution/28610451

Here j is a factor of M as it satisfies (M%j==0) and we store a corresponding value of N in mr [Explained in editorial]
Coming to the second block, we have r = M/j where j is a factor of M which means r is a factor too eg. 5 is a factor of 10 and 10/5 = 2 is a factor of 10. So we have to add the corresponding value of N in mr for r but if r is same as j we will get repeating values of N so we put condition if(r!=j)

1 Like

Your approach is taking O(N) time.

Hi I just used use the approach:
for i = a%m to i<=m and incrementing i = i + a:
so now if((m-a)/a)%i == 0 && i != 0)
we can insert into some vector…

But this approach is giving me WA :frowning: Ik it should give some TLE but why WA?