Editorial - EXAMCHT

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Adarsh Agrawal

Tester: Radoslav Dimitrov

Editorialist: Raja Vardhan Reddy

DIFFICULTY:

Simple

PREREQUISITES:

Modular operation, divisors.

PROBLEM:

An examination is conducted with p sets of question papers. They are distributed such that, a student with roll no. r gets (r-1)%p + 1 th paper. What is the number of possible values of p such that students with roll no. A and B gets the same paper?

EXPLANATION

According to the problem, a student with roll no. r gets (r-1)\%p + 1 th paper.
So, Ram gets (A-1)\%p + 1 th paper, and Shyam gets (B-1)\%p + 1 th paper.
For both of them to get the same question paper,

(A-1)\%p + 1 = (B-1)\%p + 1
=> (A-1)\%p = (B-1)\%p
=> |A-B|\%p = 0 , |A-B| is absolute value of (A-B).

Hence, for Ram and Shyam to get the same question paper, p should be a divisor of |A-B|.
Therefore, number of values of p is equal to number of divisors of |A-B|.

  • If |A-B|=0, number of values of p is infinite.
  • If |A-B|!=0, number of divisors can be calculated in O(\sqrt|A-B|)

Refer this for more details on how to calculate the number of divisors in O(\sqrt n)

TIME COMPLEXITY:

Computation of number of divisors takes O(\sqrt(|A-B|)) time.
Total complexity : O(\sqrt(|A-B|)) for each test case.

SOLUTIONS:

Setter's Solution
#include "bits/stdc++.h"
using namespace std;
#define M 1000000007
#define U 998244353
#define N 1000005
#define int long long
#define sz(c) (int)c.size()
#define fr first
#define ll long long 
#define sc second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rep(i,a,n) for(int i=a ; i<n ; i++)
#define r0 return 0;
#define endl '\n'
#define INF (int)1e15
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
set<int> Divisors(int n) 
{ 
    set<int> ans;
    for (int i=1; i<=sqrt(n); i++) 
    {
        if (n%i == 0) 
        {
            if (n/i == i) 
                ans.insert(i);
            else
            {
                ans.insert(i);
                ans.insert(n/i);
            }
        } 
    } 
    return ans;
} 
signed main()
{
    ios_base::sync_with_stdio(0);
    int TESTS=1;
    cin>>TESTS;
    while(TESTS--)
    {   
        int a,b;
        cin >> a >> b;
        if(a==b){
        	cout<<-1<<endl;
        }
        else{
        	set<int> s = Divisors(abs(a-b));
        	cout<<sz(s)<<endl;
        }
    }   
}      
Tester's Solution
from collections import deque
 
inf = 10 ** 18
 
 
def read_line_int():
    return [int(x) for x in input().split()]
 
 
def partial_sums(iterable):
    total = 0
    for i in iterable:
        total += i
        yield total
 
 
# -----------------#
#       Main      #
# -----------------#
 
T = read_line_int()[0]
 
for test in range(T):
    a, b = read_line_int()
    x = abs(a - b)
 
    cnt = 0
    d = 1
 
    while d * d <= x:
        if x % d == 0:
            if d != x / d:
                cnt += 2
            else:
                cnt += 1
 
        d += 1
 
    if x == 0:
        print(-1)
    else:
        print(cnt)
Editorialist's Solution
//raja1999
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
 
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
 
//std::ios::sync_with_stdio(false);
 
int factors(int x){
	int i,c=0;
	for(i=1;i*i<=x;i++){
		if(x%i==0){
			c++;
			if(i*i!=x){
				c++;
			}
		}
	}
	return c;
}
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t,t1;
	cin>>t;
	t1=t;
	while(t--){
		int a,b;
		cin>>a>>b;
		if(a==b){
			cout<<"-1"<<endl;
			continue;
		}
		if(a>b){
			swap(a,b);
		}
		cout<<factors(b-a)<<endl;
	}
	return 0;
} 

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

3 Likes

Bro in th constraint it is given that a and b cannot be equal it means a-b can never be zero then how you conclude it that infinite value can exist?
Also r-1%p th set they get but you are using r-1%p+1 th val.
Can you elaborate??

6 Likes

bro there would be no difference as it is being cancelled out the trick of the problem was to find all the factors of |A-B|or find all numbers satisfying |A-B|%p==0.

Read the comment under the question https://www.codechef.com/COOK114B/problems/EXAMCHT

how (A-1)%p = (B-1)%p
=> |A-B|%p = 0?

6 Likes
  1. (A-1)%p=(A%p)-(1%p)
    so we can write the equation as (A%p)-(1%p)=(B%p)-(1%p)
    now cancel (1%p) on both sides then you get (A%p)=(B%p)
    equate the above equation to 0
    (A%p)-(B%p)=0 so by the property mentioned on the first line the equation becomes (A-B)%p
    Hope you understand
6 Likes

thank you @nihith123. Can you suggest me some reference to learn about mod operations.


property no. 3 under the topic modulo arithmetic and quoted part

can anyone please tell me which one is correct and how?

all three lines are correct ,you start from “(A−1)%p=(B−1)%p” and solve it to get
|A-B|%p = 0 , this statement tells you need to count all the factors of of “|A-B|”, we have used modulus as there are possible cases when B>A too. to do so we use “abs” keyword in c++.

can modulo operator give negative values? if yes ok! if no then how to remove negative sign ? by adding the value for which modulus is taken or by just taking absolute value of the answer? bcoz in hackerearth they hav added the value. i just want to clarify that !

nope bro ,we use modulo operator to get +ve values only . for example let A=3
B=5 ,here (A-B)=-2 is negative but we use modulus and output is 2.

we use “abs” keyword in c++ for this .

we do this

can you please explain me why you have used this condition?

1 Like

Why count += 1 ,if (n/i) =i , else count +=2

Thanks bro

when will the ans result in -1 … as in for what test case!?
also, what should be the condition to check it !?

1 Like

Because ->
if i == n/i it means i is the square root of n and therefore we would count it as one
else i and n/i are two different divisors therefore we would count both of them

please tell me how a==b is possible ?

the ans is accepted without taking this condition

(a-1)%p=(b-1)%p

((a-1)%p)-((b-1)%p)=0

[((a-1)%p)-((b-1)%p)]%p=0%p =0
[as -->(1<p<10^8)]

[((a-1)%p)-((b-1)%p)]%p = (a-1-b+1)%p=(a-b)%p
(by standard property of mod)