PROBLEM LINK:
Setter: Ritesh Gupta
Tester: Radoslav Dimitrov
Editorialist: Teja Vardhan Reddy
DIFFICULTY:
Easy
PREREQUISITES:
Math
PROBLEM:
Given n consecutive positive number which are k,k+1,k+2,...,k+n-1 respectively. Find the count of numbers that cannot represented as \sum\limits_{i=0}^{n-1}a_i* (k+i) where a_i>=0 \forall i and \sum\limits_{i=0}^{n-1}a_i \gt 0.
EXPLANATION
Firstly, we can never get numbers which are less than k.
Now using only one of the numbers we can get k,k+1,k+2,....k+n-1.
Using two numbers,we can get 2*k,2*k+1,2*k+2,....2*(k+n-1).
Similarly using x numbers , we can get x*k,x*k+1,.....x*(k+n-1).
Now , the other numbers we miss will be between k+n-1 and 2*k
similarly 2*(k+n-1) to 3*k
And x*(k+n-1) to (x+1)*k
Now since n-1>0 (from contraints), after a certain value of x, x*(k+n-1)+1 \geq
(x+1)*k.
So after that onwards, all the numbers can be attained.
x*(n-1) \geq k-1 or x \geq ceil(\frac{k-1}{n-1}) (lets call this val).So for x \lt val, we need to take sum of (x+1)*k - x*(k+n-1).
which will be nothing but \sum\limits_{x=1}^{val-1}(k-x*(n-1)).
= k*(val-1)-(n-1)*\sum\limits_{x=1}^{val-1}x
= k*(val-1) - (n-1)*val*(val-1)/2.
Hence, total answer will be k-1 + k*(val-1) - (n-1)*val*(val-1)/2.
TIME COMPLEXITY
The above value can be computed in O(1) time per test.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int32_t main()
{
int t;
cin >> t;
while(t--)
{
int n,k;
cin >> n >> k;
int total = (k-1)/(n-1);
int first = k-1;
int last = first - total*(n-1);
int ans = first + last;
total++;
if(ans%2 == 0)
ans /= 2;
else
total /= 2;
ans = ((ans%mod) * (total%mod))%mod;
cout << ans << endl;
}
}
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int64_t mod = (int64_t)1e9 + 7;
const int64_t inv2 = (mod + 1) / 2;
int64_t n, k;
void read()
{
cin >> n >> k;
}
void solve()
{
if(k <= n)
{
cout << (k - 1) % mod << endl;
return;
}
int64_t cnt = ((k - n) / (n - 1)) % mod, answer = ((((k - n) % (n - 1)) % mod) * (cnt + 1)) % mod;
cnt = cnt * 1ll * (cnt + 1) % mod;
cnt = cnt * 1ll * inv2 % mod;
cnt = (cnt * 1ll * ((n - 1) % mod)) % mod;
answer = (answer + cnt) % mod;
answer = (answer + k - 1) % mod;
cout << answer << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
while(T--)
{
read();
solve();
}
return 0;
}
Editorialist's Solution
//teja349
#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); 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 flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define int ll
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
n--;
int wow,gg,val=(k-1)/n;
if(val%2){
wow=val+1;
wow/=2;
wow%=mod;
wow*=(val%mod);
}
else{
wow=val;
wow/=2;
wow%=mod;
wow*=((val+1)%mod);
}
val%=mod;
wow%=mod;
gg=(k-1)%mod;
val%=mod;
gg*=val;
gg%=mod;
wow*=n;
wow%=mod;
gg-=wow;
gg%=mod;
gg+=mod;
gg+=k-1;
gg%=mod;
cout<<gg<<endl;
}
return 0;
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
