 # Editorial - EXAMCHT

Practice

Contest: Division 1

Contest: Division 2

Editorialist: Raja Vardhan Reddy

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

return [int(x) for x in input().split()]

def partial_sums(iterable):
total = 0
for i in iterable:
total += i
yield total

# -----------------#
#       Main      #
# -----------------#

for test in range(T):
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 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. 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