# ICPC 2019 Preli: G – Pairs Forming GCD

0

Solution Idea:

• We have to find maximum G such that there exist at least P pairs of integers (X, Y), where 1 ≤ X ≤ Y ≤ N and GCD(X, Y) = G.
• At first, let’s try to solve a subproblem where G=1. Can we calculate the number of pairs (X, Y) where 1 ≤ X ≤ Y ≤ N and GCD(X, Y) = 1?
• As we know Euler totient or Phi function gives us a number of X which are coprime with Y. So Phi(Y) = number of X such that GCD(X,Y) = 1.
• So Phi(1)+Phi(2)+Phi(3)+…….+Phi(N) = number of pair (X,Y) where 1 ≤ X ≤ Y ≤ N and GCD(X, Y) = 1.
• Now if GCD(X,Y) = 1 then GCD(GX,GY) = G.
• So we can pre-calculate Euler totient for 1 to N and then calculate the cumulative sum of this phi[] array and store it to phiSum[] array.
• After this, we just have to binary search for the maximum answer on the new phiSum[] array.

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

using namespace std;

#define mx 10000007
int phi[mx];
long long phiSum[mx];

void euler_totient() {
for(int i=0; i<mx; i++) phi[i]=i;
for(int i=2; i<mx; i++) {
if(phi[i]==i) {
for(int j=i; j<mx; j+=i)
phi[j]-=(phi[j]/i);
}
}
}

int solve(int n, long long p) {
int lo=1,hi=n;
int ret=-1;
while(lo<=hi) {
int mid=(lo+hi)/2;
if(phiSum[mid]>=p) {
ret=mid;
hi=mid-1;
} else {
lo=mid+1;
}
}
return ret;
}

int main() {

euler_totient();
for(int i=1; i<mx; i++) phiSum[i]+=phiSum[i-1]+phi[i]; //cumulative sum

int t;
scanf("%d",&t);
for(int z=1; z<=t; z++) {
long long n,p;
scanf("%lld %lld",&n,&p);
int ans=solve(n,p);
printf("Case %d: ",z);
if(ans!=-1)
ans=n/ans;
printf("%d\n",ans);
}
return 0;
}```

# SPOJ: SQFREE – Square-free integers

0

Solution Idea:

Basic operation of mobius function. Generate mobius function. Then think about every number whose mobius function value is not zero. If we squre them then something we can get.

```
#include &lt;bits/stdc++.h&gt;

#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)

#define ss               second
#define sqr(x)           (x)*(x)

#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)

#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define ll long long

using namespace std;

#define mx 10000007

int ara[mx];
vector&lt;ll&gt;num,mobius,prime;
bitset&lt;mx/2&gt;vis;

void sieve()
{
int x=mx/2,y=sqrt(mx)/2;

for(int i=1;i&lt;y;i++)
{
for(int j=i*(i+1)*2;j&lt;x;j+=(2*i+1))
vis[j]=1;
}

prime.pb(2);
for(int i=3;i&lt;mx;i+=2)
if(vis[i/2]==0)
prime.pb(i);

}

void precal()
{
fill(ara,ara+mx,1);
for(int i=0;prime[i]*prime[i]&lt;mx;i++)
{
ll x=prime[i]*prime[i];
for(int j=x;j&lt;mx;j+=x)
ara[j]=0;
}

for(int i=0;i&lt;SZ(prime);i++)
{
int x=prime[i];
for(int j=x;j&lt;mx;j+=x)
ara[j]*=-1;
}

for(int i=2;i&lt;mx;i++)
{
if(ara[i]==0) continue;
num.pb(i);
mobius.pb(ara[i]);
}

}

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);
sieve();
precal();

int t;
sf(t);
TEST_CASE(t)
{
ll n;
sfl(n);

ll ans=n;

for(int i=0;i&lt;SZ(num);i++)
{
ll x=num[i];
ll zz=sqr(x);
if(zz&gt;n) break;
int y=mobius[i];
ans+=mobius[i]*(n/zz);
}

printf(&quot;%lld\n&quot;,ans);

}

return 0;
}

```

# nCr%m when m is not prime and n and r is sufficiently large.

1

In many problems we need to calculate nCr%m where n, r and m are three positive integers. If the mod value m is a prime number then we can calculate nCr%m in different ways like using loops, using pascal’s triangle, using modular multiplicative inverse, using dp technique etc. This ways are described with source codes in this post.

Now our problem arrive when the mod value m is not prime. In this case we can’t use the above techniques. In this case we need to use the chinese remainder theorem (CRT) and Andrew Granville’s theory for calculating nCr. Here I provide you some ways to learn this techniques. I think this ways will be helpful to you.

1. First learn about chinese remainder theorem (CRT). You can learn it form these sources-
a. geeksforgeeks 1
b. geeksforgeeks 2

2. Second you can have a look on Andres Granville’s theory. The theory is explained here.

3. Now you can have a look on this problem. The detailed algorithm for our job is explained in this problem’s editorial section.

4. Now you can try to implement the algorithm. If you find any difficulties after several tries then you can see my implementation. Which is given below.

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//----------------------Graph Moves----------------
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
//------------------------------------------------

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
//------------------------------------------------

#define mx 1000006

bitset&lt;mx/2&gt;vis;
vector&lt;int&gt;prime;

vector&lt;pii&gt;factor;

void sieve()
{
int x=mx/2,y=sqrt(mx)/2;
for(int i=1; i&lt;=y; i++)
{
if(vis[i]==0)
{
for(int j=i*(i+1)*2; j&lt;x; j+=(2*i)+1)
vis[j]=1;
}
}

prime.pb(2);

for(int i=3; i&lt;mx; i+=2)
if(vis[i/2]==0)
prime.pb(i);

}

ll factorial[mx];
ll arr[mx];

vector&lt;ll&gt;ans;

void precal(ll p, ll q, ll mod)
{
arr[0]=1;
arr[1]=1;
//    ll mod=bigmod(p,q,MOD);
ll x=1;
for(ll i=2; i&lt;=mod; i++)
{
if(i%p)
x=i;
else
x=1;
arr[i]=(arr[i-1]*x)%mod;
}
}

ll bigmod(ll n, ll p, ll mod)
{
ll ret=1;
while(p)
{
if(p%2)
ret=(ret*n)%mod;
n=(n*n)%mod;
p/=2;
}
return ret;
}

ll E(ll n, ll p)
{
ll ret=0;
while(n)
{
ret+=n/p;
n=n/p;
}
return ret;
}

ll f(ll n, ll mod)
{
ll ret=bigmod(arr[mod-1],n/mod,mod)*arr[n%mod];
return ret;
}

ll F(ll n, ll mod, ll p)
{
ll ret=1;
ll i=1;
while(i&lt;=n)
{
ret=(ret*f(n/i,mod))%mod;
i=i*p;
}
return ret;
}

int inv(int a, int m) // Calculating Modular Multiplicative Inverse
{
int m0 = m, t, q;
int x0 = 0, x1 = 1;

if (m == 1)
return 0;

//     Apply extended Euclid Algorithm
while (a &gt; 1)
{
//         q is quotient
q = a / m;

t = m;

//         m is remainder now, process same as
//         euclid's algo
m = a % m, a = t;

t = x0;

x0 = x1 - q * x0;

x1 = t;
}

//     Make x1 positive
if (x1 &lt; 0)
x1 += m0;

return x1;
}

ll nCr(ll n, ll r, ll p, ll mod)
{
ll e=E(n,p)-E(r,p)-E(n-r,p);
ll mod1=F(n,mod,p);
ll mod2=(F(r,mod,p)*F(n-r,mod,p))%mod;
mod2=inv(mod2,mod);
ll ret=bigmod(p,e,mod);
ret*=mod1;
ret%=mod;
ret*=mod2;
ret%=mod;
return ret;
}

ll findMinX(int k) // Chinese Remainder
{
ll prod = 1;
vector&lt;int&gt;num;
for(int i=0; i&lt;k; i++)
{
num.pb(bigmod(factor[i].ff,factor[i].ss,MOD));
}
for (int i = 0; i &lt; k; i++)
prod *= num[i];

ll result = 0;

for (int i = 0; i &lt; k; i++)
{
ll pp = prod / num[i];
result += ans[i] * inv(pp, num[i]) * pp;
}

return result % prod;
}

ll nCr_mod_m(ll n, ll r, ll m)
{
factor.clear();
ans.clear();
int root=sqrt(m);
ll mm=m;
for(int i=0; i&lt;SZ(prime) &amp;&amp; prime[i]&lt;=root; i++)
{
if(mm%prime[i]==0)
{
int cnt=0;
while(mm%prime[i]==0)
{
mm/=prime[i];
cnt++;
}
factor.pb(pii(prime[i],cnt));
root=sqrt(mm);
}
}

if(mm&gt;1)
factor.pb(pii(mm,1));

for(int i=0; i&lt;SZ(factor); i++)
{
ll p=factor[i].ff;

ll num=bigmod(p,factor[i].ss,MOD);
precal(p,factor[i].ss,num);
ans.pb(nCr(n,r,p,num));
}

ll anss=findMinX(SZ(factor));
return anss;
}

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

sieve();

int t;
sf(t);
TEST_CASE(t)
{
ll n,r,m;
cin&gt;&gt;n&gt;&gt;r&gt;&gt;m;

ll ans=nCr_mod_m(n,r,m);

pf(&quot;%lld C %lld mod %lld = %lld\n&quot;,n,r,m,ans);
}

return 0;
}

```

Practice problems:
1. nCr
2. Codechef’s Long Sandwich(SANDWICH).

# Light OJ: 1326 – Race

0

Solution Idea:

Let’s define dp(i) as the number of ways in which a race with “i” horses can finish.

Suppose we have “i” horses at the race and we will choose k of them for the first place, leaving “i – k” for the second (or higher) place. The process to count the number of ways to choose horses for the second place is equals to the original problem. This is the reason why we use dp.

(This Solution idea is from Manuel Pinda)

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              10056
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

ll dp[1003][1003];
ll ans[1003];

ll nCr(int n, int r)
{
if(r==1) return n;
if(n==r) return 1;

ll &amp;ret=dp[n][r];

if(ret!=-1) return ret;

return ret=(nCr(n-1,r-1)%MOD+nCr(n-1,r)%MOD)%MOD;
}

ll func(int n)
{
if(n==0) return 1;
if(ans[n]!=-1) return ans[n];

ll ret=0;

for(int i=1;i&lt;=n;i++)
{
ret+=(nCr(n,i)*func(n-i))%MOD;
ret%=MOD;
}

return ans[n]=ret;
}

int main()
{

//freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int t;
sf(t);

ms(dp,-1);
ms(ans,-1);

TEST_CASE(t)
{
int n;
sf(n);
PRINT_CASE;

printf(&quot;%lld\n&quot;,func(n));

}

return 0;
}

```

# Light OJ: 1102 – Problem Makes Problem

0

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

ll fact[2000006];

ll bigmod(ll n, ll pow)
{
ll ret=1;
while(pow)
{
if(pow%2==1)
{ret*=n; ret%=MOD;}
n*=n;
n%=MOD;
pow/=2;

}
return ret;
}

int main()
{

//freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);
fact[0]=1;
for(ll i=1;i&lt;2000005;i++)
{
fact[i]=(fact[i-1]*i)%MOD;
}

int t;
sf(t);
TEST_CASE(t)
{
int n,k;

sff(n,k);

ll down=(fact[k-1]*fact[n])%MOD;

down=bigmod(down,MOD-2);

down=(fact[n+k-1]*down)%MOD;

PRINT_CASE;

printf(&quot;%lld\n&quot;,down);

}

return 0;
}

```

# Light OJ: 1095 – Arrange the Numbers

0

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

ll fact[1005];

ll dp[1005][1005];

ll nCk(int n, int k)
{
if(k==1) return n;
if(n==k) return 1;

if(dp[n][k]!=-1) return dp[n][k];

return dp[n][k]= (nCk(n-1,k-1)+nCk(n-1,k))%MOD;
}

int main()
{

//freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

fact[0]=1;

for(ll i=1; i&lt;1002; i++) fact[i]=(fact[i-1]*i)%MOD;

int t;
sf(t);
ms(dp,-1);

TEST_CASE(t)
{
ll n,m,k;
sfffl(n,m,k);
ll ans=nCk(m,k);

int nn=n-k;

ll ans1=fact[n-k];

for(int i=1; i&lt;=(m-k); i++)
{
if(i%2==1)
ans1-= (nCk(m-k,i)*fact[nn-i])%MOD;
else
ans1+= (nCk(m-k,i)*fact[nn-i])%MOD;
ans1=(ans1+MOD)%MOD;
}

PRINT_CASE;

printf(&quot;%lld\n&quot;,(ans*ans1)%MOD);

}

return 0;
}

```

# UVa 10139 – Factovisors

0

Solution Idea:

Calculate the prime factor of M. Let a prime is P and it’s power is x. so P^x is a prime factor of M. then check that in N! prime factor of P is grater or equal to x.

```

#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

#define mx 100000

bitset&lt;mx/2&gt; vis;

vector&lt;int&gt;prime;

void sive()
{
int x=mx/2,y=sqrt(mx)/2;

for(int i=1; i&lt;y; i++)
{
if(vis[i]==0)
{
for(int j=i*(i+1)*2; j&lt;x; j+=(2*i)+1)
vis[j]=1;
}
}

prime.pb(2);
for(int i=3; i&lt;mx; i+=2)
if(vis[i/2]==0)
prime.pb(i);

}

int main()
{
CIN;
//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

sive();

ll n,m;
while(cin&gt;&gt;n&gt;&gt;m)
{
ll a,b;
a=n,b=m;
ll root=sqrt(m)+1;
bool test=0;
//        if(m==0) test=1;
for(int i=0;prime[i]&lt;root;i++)
{
if(m%prime[i]==0)
{
int cnt=0;
while(m%prime[i]==0)
cnt++,m/=prime[i];
ll temp=n;
ll sum=0;
while(temp)
{
sum+=temp/prime[i];
temp/=prime[i];
}
if(sum&lt;cnt)
{
test=1;
break;
}
root=sqrt(m)+1;
}
}
if(m&gt;1)
{
ll temp=n;
ll sum=0;
while(temp)
{
sum+=temp/m;
temp/=m;
}
if(sum&lt;1)
{
test=1;
}
}

if(test==0)
cout&lt;&lt;b&lt;&lt;&quot; divides &quot;&lt;&lt;a&lt;&lt;&quot;!&quot;&lt;&lt;endl;
else
cout&lt;&lt;b&lt;&lt;&quot; does not divide &quot;&lt;&lt;a&lt;&lt;&quot;!&quot;&lt;&lt;endl;
}

return 0;
}

```

# 10673 – Play with Floor and Ceil

0

Solution Idea:

Straight forward implementation.

Just calculate a and b of extended euclid algorithm and pass it to extended euclid function. don’t worry about sample input and output 😛

```

#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

ll extended_euclid(ll a, ll b, ll &amp;x, ll &amp;y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
ll x1,y1;
ll ret=extended_euclid(b,a%b,x1,y1);
x=y1;
y=x1-y1*(a/b);
return ret;
}

int main()
{

///freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int t;
cin&gt;&gt;t;
TEST_CASE(t)
{
ll x,k;
cin&gt;&gt;x&gt;&gt;k;
ll a=x/k;
ll b=(x/k)+ ((x%k)?1:0);

ll xx,yy;

ll gcdd=extended_euclid(a,b,xx,yy);
x/=gcdd;
xx*=x;
yy*=x;
cout&lt;&lt;xx&lt;&lt;&quot; &quot;&lt;&lt;yy&lt;&lt;endl;

}

return 0;
}

```

# UVa 10090 – Marbles

0

Solution Idea: first check if it is possible or not to get a valid result. If possible then get one result with extended euclid algo and then check the result taking minimum type 1 box and then check the result taking minimum type 2 box. print the minimum value.

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

ll extended_euclid(ll a, ll b, ll &amp;x, ll &amp;y)
{
if(b==0)
{
x=1,y=0;
return a;
}
ll x1,y1;
ll ret=extended_euclid(b,a%b,x1,y1);
x=y1;
y=x1-y1*(a/b);
return ret;
}

int main()
{
CIN;
//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

ll n;
while(cin&gt;&gt;n &amp;&amp; n)
{
ll c1,n1,c2,n2;
cin&gt;&gt;c1&gt;&gt;n1&gt;&gt;c2&gt;&gt;n2;

bool test=0;

if(n % __gcd(n1,n2))
{
cout&lt;&lt;&quot;failed&quot;&lt;&lt;endl;
}
else
{
ll x,y;
ll gcdd=extended_euclid(n1,n2,x,y);
x*=(n/gcdd);
y*=(n/gcdd);

n1/=gcdd;
n2/=gcdd;

ll aa=ceil(-(double)x/n2);
ll bb=floor((double)y/n1);

if(aa&lt;=bb)
{
if(c1 * (x + n2 * aa) + c2 * (y- n1*aa) &lt; c1*(x+(n2*bb)) + c2*(y-n1*bb))
{
x+=n2*aa;
y-=n1*aa;
}
else
{
x+=n2*bb;
y-=n1*bb;
}
}
else
test=1;

if(test)
cout&lt;&lt;&quot;failed&quot;&lt;&lt;endl;
else
cout&lt;&lt;x&lt;&lt;&quot; &quot;&lt;&lt;y&lt;&lt;endl;

}

}

return 0;
}

```

# UVa 10104 – Euclid Problem

0

Solution Idea: Straight forward implementation of extended euclid algo.

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

ll extended_euclid(ll a, ll b, ll &amp;x, ll &amp;y)
{
if(b==0)
{
x=1;y=0;
return a;
}
ll x1,y1;
ll temp=extended_euclid(b,a%b,x1,y1);
x=y1;
y=x1-y1*(a/b);
return temp;
}

int main()
{

///freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

ll a,b;
while(sffl(a,b)==2)
{
ll x,y,z;
z=extended_euclid(a,b,x,y);
pf(&quot;%lld %lld %lld\n&quot;,x,y,z);
}

return 0;
}

```