Chef and Ingredients wrong on sub task- 2 task -1

1

I am a beginner don’t know much about modular arithmetic please tell if there is any logical problem in my solution or it is due to modular arithmetic :
https://www.codechef.com/viewsolution/24830452

2 Likes
2

a/2%mod=a*modinverse(2,mod)

3

what is modinverse can u tell me.

4
5

You must be getting overflow here use a larger int type.

6

I am alredy using long long int

7

you should have tried cpp_int from boost

8

use

#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;

and following to declare integer of larger size.

int128_t mod=1000000007;

This will create an integer of 128 bit. So no problem of overflow.

9

Use int128_t instead.

1 Like
10

Hi, this can be narrowed down to a very simple one liner

#include <iostream>
#include <bits/stdc++.h>

#define ll long long int
#define MOD 1000000007
#define INV 500000004

using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        ll n,k;
        cin>>n>>k;

        if(k==1){
            cout<<0<<endl;
            continue;
        }

        ll a = k;
        ll s = n-1;
        ll t = (a-2)%s;

        ll cardinality = (((((((a-2)/s)+1)%MOD)*(((a%MOD+t%MOD)%MOD)%MOD))%MOD)*INV)%MOD;

        cout<<cardinality<<endl;

    }
    return 0;
}
1 Like
11

Thanks it worked learned something new.

12

Thank you it worked learne something new

13

Simple solution without using modular inverse.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i(0);i<n;i++)
#define fast  ios_base::sync_with_stdio(0); cin.tie(0);
#define mod 1000000007
#define pb push_back
#define all(v) v.begin(), v.end()

int cl(int a, int b){
    if(a%b != 0)return (a - a%b + b)/b;
    return a/b;
    }

int32_t main() {
    fast;


int t;
cin>>t;

while(t--){
    int n,k;
    cin>>n>>k;
    int terms = cl(k-1, n-1),ans;
    ans = 2*(k-1) - (terms - 1)*(n-1);
    if(terms&1){
    	ans/=2;
	    ans%=mod;
	    terms%=mod;
    }
    else{
	    terms/=2;
	    terms%=mod;
	    ans%=mod;
    }
    ans*=terms;
    ans%=mod;
    cout<<ans<<"\n";   
}
return 0;

}

I did MOD as many times as I could do.

2 Likes
14

Is it something like if you use return type of main as int32_t, all int are considered as long long int? Can you explain this please? I had seen article (maybe on geeksforgeeks) somewhere but cant find it. Please mention resources if you find any! @satyankar_2005 @l_returns

15

See C++ code here to understand better.

16

or divide all even numbers beforehand by 2 and take mod

17

What I have done is defined int as a macro for long long int. But main function only returns int not a long long. So I have specified that a 32-bit integer int32_t will be used with main

18

Oh okay. Got it. Thanks :blush: But can you explain different between regular int and int32_t? They seems same. I searched a bit but didn’t found any satisfactory results. @satyankar_2005