Codeforces

1

https://codeforces.com/contest/1352/problem/C

How to solve this problem??

2 Likes
2 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define lld long long int 

int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        lld n,k;
        cin>>n>>k;
        lld val1=k/n;
        k+=val1;
        lld val2=k/n;
        lld val3=val2-val1;
        k+=val3;
                    //cout<<k<<" "<<val1<<" "<<val2<<"\n";

        while(val3!=0)
        {
            val1=k/n;
            val3=abs(val1-val2);
            k+=val3;
            val2=k/n;
            k+=abs(val2-val1);
            //cout<<k<<" "<<val1<<" "<<val2<<"\n";
        }
        cout<<k<<"\n";
        
    }
}

You have to simply count how many numbers are divisible by n. Add that quantity to k. But after this addition again some more numbers are divisible by n. So, you have to add that amount again.Do this until the new k has not any new divisible number

3

We can use these two observations to form a solution:

  1. Every number smaller than n is not divisble by n.
  2. Starting from n, every number after (n-1) numbers is a multiple of n.
void solve() {
  lli n, k;
  cin >> n >> k;
  if(k<n)
    cout << k << endl;
  else {
    k -= n;
    cout << n*((k)/(n-1)+1) + (k)%(n-1) + 1<< endl;
  }
}
4

Think in terms of binary_search.
For any integer x such that (x%n==0), it position in multiples of n is given by pos = (x/n),
hence its position in non multiples of n, where (x%n!=0) is given by, pos = x - x/n.
Now, if pos>K, update high = x - 1,
else update low = x + 1 and ans = x.

1 Like
5

Can u show your full code please? I can’t implement it.

6 
#include "bits/stdc++.h"
using namespace std;

#define ll       long long int 
#define lct      ll t;cin>>t;while(t--)

void fast_io(){
    ios::sync_with_stdio(false);cin.tie(0);
    #ifndef ONLINE_JUDGE
        freopen ("in.txt","r",stdin);
        freopen ("out.txt","w",stdout);
    #endif
}

const ll N = 2*1e9 + 7;

int32_t main(){
    fast_io();

    ll n,k,l,r,ans,pos,mid;
    string s;
    lct{
        cin>>n>>k;
        l = 1, r = N;
        ans = -1;
        while(l<=r){
            mid = (l+r)/2;
            pos = mid - mid/n;
            if(pos>=k){
                r = mid-1;
                ans = mid;
            }else{
                l = mid+1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
7

its simple;
print(k+(k-1)//(n-1))

3 Likes
8 
for ix in range(int(input())):
    n, k = map(int, input().split())
    x=k%(n-1)
    k-=x
    aa=n*(k//(n-1))+x
    if aa%n==0:
        aa-=1
    print(aa)
9

If you use binary search you don’t even need to pick up pen to formulate. Read the question and code.

Implementation 
void solve(int test_case){
	ll n,k;
	cin >> n >> k;
	ll hi = LLONG_MAX >> 10;
	ll lo = 1;
	ll ans = hi;
	while(lo <= hi){
		ll mi = lo + hi >> 1;
		ll p = mi - mi/n;
		if(p >= k){
			ans = mi;
			hi = mi-1;
		}else{
			lo = mi+1;
		}
	}
	cout << ans << "\n";
}
10

Can someone explain me why the approach is K-1/N-1 in [C - K-th Not Divisible by n]

  1. as of my thinking that K-1 is because for k there are k-1 non divisible terms okay.
  2. i read a comment about cycles for N… but shouldn’t it be simply N and not N-1.

thanks in advance.

11

Dry run this for a 2 to 3 test cases and you will get it.

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define SUP INT_MAX
#define INF INT_MIN
#define SSUP LLONG_MAX
#define IINF LLONG_MIN
#define W while
#define ff first
#define ss second
#define vll vector
#define pll pair<ll,ll>
#define vpll vector
#define vvll vector
#define it(r,v) for(auto r=v.begin();r!=v.end();r++)
#define all(v) v.begin(),v.end()
#define in insert
#define FOR(i,n) for(ll i=0;i<n;i++)
#define space cout<<"\n\n";
#define endl ‘\n’
using namespace std;
const ll M = 1e9 + 7;

int main()
{
#ifndef ONLINE_JUDGE
freopen(“input2.txt”, “r”, stdin);
freopen(“output3.txt”, “w”, stdout);
#endif
FIO
ll t; cin >> t;

W(t--) {
	ll n, k; cin >> n >> k;
	ll m = n - 1;
	ll tt = k / m;
	if (k % m == 0) {
		tt--;
	}
	ll t1 = tt * m;
	ll t2 = tt * n;
	ll diff = k - t1;
	ll ans = t2 + diff;
	cout << ans << '\n';
}
return 0;

}

2 Likes