If n - 2 is not a multiple of 3, a = 1, b = 1, c = n - 2 is OK.

Otherwise, a = 1, b = 2, c = n - 3 is OK.

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	if((n-2)%3)printf("1 1 %d",n-2);
	else printf("1 2 %d",n-3);
}

To cover a point (x_i, y_i), the length of the shorter side of the triangle should be at least x_i + y_i.

So the answer is max(x_i + y_i).

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,x,y,ans=0;
	scanf("%d",&n);
	while(n--)scanf("%d%d",&x,&y),ans=max(ans,x+y);
	printf("%d",ans);
}

First we divide all numbers by GCD of them. Then we should find a subset with maximum number of integers GCD of which is bigger than 1.

We can enumerate a prime p that GCD of the remaining integers can be divided by. And the number of integers can be divided by p is the maximum size of the subset.

We can use Sieve of Euler to factor all integers in time. Then we find the prime that can divide most integers. The answer is n minus the number of integers can be divided by this prime. If all integers are 1 (after dividing their GCD), there is no solution.

#include<bits/stdc++.h>
using namespace std;
#define MN 300000
#define MX 15000000
int a[MN+5],u[MX+5],p[MX+5],pn,s[MX+5];
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int main()
{
	int n,i,j,g,x,ans=0;
	for(i=2;i<=MX;++i)
	{
		if(!u[i])u[i]=p[++pn]=i;
		for(j=1;i*p[j]<=MX;++j){u[i*p[j]]=p[j];if(i%p[j]==0)break;}
	}
	scanf("%d",&n);
	for(g=0,i=1;i<=n;++i)scanf("%d",&a[i]),g=gcd(g,a[i]);
	for(i=1;i<=n;++i)for(j=a[i]/g;j>1;)for(++s[x=u[j]];u[j]==x;)j/=u[j];
	for(i=1;i<=MX;++i)ans=max(ans,s[i]);
	printf("%d",ans?n-ans:-1);
}

It seems that many people is unsatisfied with the constraints of this problem :( I'm sorry very very much!

Now I'll explain the reason of the constraints.

First, about the main idea of this problem, both FallDream and me thought it's only the prime factors must be considered (Certainly, when the GCD of all the integers is 1).

So I think solutions which consider each prime should be able to pass but which consider all the factors should not.

In the beginning, the maximum of n is 5·10⁵ and of a_i is 10⁷, and the time limit is also 1s. My solution will run for less than 0.4s.

Then the tester cyand1317 submit a solution with time (Let A denote the maximum of a_i) which count the number of multiples for each number. His solution got TLE but just ran for about 1s. I think this solution do not use the main idea, so should be not able to pass. Then I increased the limit of a_i a little to 1.5·10⁷ so that his solution should run for about 1.5s. Since the solution with time should use the main idea and I think it should be able to pass, I do not increase it too much. And according to cyand1317's suggestion, the time limit is unfriendly to some languages, I reduced n to 3·10⁵ so that there will be less constant requirement for standard solutions. Then my solution will run for about 0.3s and solutions will run for about 0.6s (and it seems that running on codeforces is a little bit faster than running on polygon). I thought this result is acceptable so it became the final constraints.

If the constraints make you feel unfriendly, I'm sorry very very much once again! There are so many conditions I should consider that I worried about it for a long time and do not receive a good result finally :( And I did not notice that the brute force can care only primes not bigger than so many of them got AC :(

Also sorry for too weak pretests.

Hope you can forgive me for my mistakes.

Following the rules in the problem, the 1 × 6, 2 × 4, 2 × 5 and 3 × 4 grids full of chessmen can be easily constructed.

Assume that n ≤ m. Consider the following cases:

If n = 1, obviously the answer is .

If n = 2, only the 2 × 2, 2 × 3 and 2 × 7 grids cannot be completely constructed. The others can be constructed by using the 2 × 4, 2 × 5 and 2 × 6(constructed by two 1 × 6 grids) girds.

If n > 2, the following things we can consider:

We know that using the 2 × 4 and 3 × 4 grids we can construct the 4 × x(x > 2) grid, and using several 1 × 6 grids we can construct the 6 × x(x > 2) grid, so using the 4 × x and 6 × x grids we can construct the x × y grid while x, y > 2 and y is an even number.

Therefore we only need to consider the n × m grid that n and m are both odd numbers.

Since n × m is an odd integer, we can place nm - 1 chessmen at most, so we try to reach the maximum.

Then we can easily construct the 3 × 3, 3 × 5 and 5 × 5 grids that have only one empty grid. According to the above-mentioned conclusions, any n × m grids can be reduce to one of the three grids by using some x × y(x or y is even) grids. The maximum is reached.

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	if(n>m)swap(n,m);
	if(n==1)printf("%d",m/6*3+max(m%6-3,0)<<1);
	else if(n==2)printf("%d",m==2?0:m==3?4:m==7?12:m<<1);
	else printf("%lld",1LL*n*m/2*2);
}

This problem is a matching problem. And we found that two grids can be matched only if they have different parities of the sum of two coordinates. So it's actually a biparite graph matching problem :) So we can calculate the answer for all small n and m. When n = 1 or m = 1, the answer is easy to get. Otherwise, we found that if n or m is big enough, the answer will be the maximum. So just keep the answers for small n and m, you will get AC easily :)

First, we try to find whether it's possible to separate the kingdom into k regions of level-2 with the same sum of values. We calculate S, the sum of all the values, so each region should have sum . Let s_i be the sum of values in the subtree of root i. We consider all the cities from the leaves to the root, when a subtree i has sum , separating it from the tree. We find that only the i with will be considered. So there should be at least k cities satisfying this condition. And if there exist such k cities, we cut the edge to their father (if it is not the root), so the size of each connected part will be multiple of . Since all the values are positive, all the connected parts have size . So we just need to count how many cities i with there are. Let the equation be , where x is a positive integer, so k should be a multiple of . Now we can use a simple dp with time to find whether it's possible to separate the kingdom into k regions of level-2 for all the k.

And it's not difficult to find that there can be k_i regions of level-i if and only if there can be k_i regions of level-2 and k_i - 1 is a factor of k_i. Let f_i be the number of plans with i regions of the last level, and we enumerate the factors of i to transform. So the total time of this solution is (including the time to calculate the gcd).

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MN 1000000
#define MOD 1000000007
ll s[MN+5];int f[MN+5],p[MN+5],F[MN+5];
inline void rw(int&x,int y){if((x+=y)>=MOD)x-=MOD;}
int main()
{
	int n,i,j,ans=0;
	scanf("%d",&n);
	for(i=1;i<=n;++i)scanf("%lld",&s[i]);
	for(i=2;i<=n;++i)scanf("%d",&p[i]);
	for(i=n;i>1;--i)s[p[i]]+=s[i];
	for(i=n;i;--i)if((s[i]=s[1]/__gcd(s[1],s[i]))<=n)++f[s[i]];
	for(i=n;i;--i)for(j=i;(j+=i)<=n;)f[j]+=f[i];
	for(F[1]=i=1;i<=n;++i)if(f[i]==i)for(rw(ans,F[j=i]);(j+=i)<=n;)rw(F[j],F[i]);
	printf("%d",ans);
}

It seems that solution can pass this problem? Some of the testers submit solutions which enumerate the multiples of instead of keep them in an array and then use a dp. I think its time complexity will be , but I can not prove it's a tight upper bound. I try to construct tests but get 1.5·10⁸ times of calculation at most which their solutions should run for about 1.5s and my solution should run for about 1s.

And I could not construct tests whose answer is bigger than 10⁹ + 7. So you may get AC even though you mistake the modulo number or do not modulo :D I guess the answer will be about (just guess). Can someone tell me about it, please?

Lastly, about the generator, I spent a whole afternoon to write it and its length is about 4kb which seems to be longer than the total length of my code for all problems! (As you can see, my code is always a little shoter than most of people) I hope the tests are strong enough :)

First we consider how to calculate the value of an interval of intervals [l, r]. We can consider intervals in order from 1 to n and, for each position on the axis, maintain a timestamp denoting the last time it was covered. When the r-th interval is taken into consideration, the timestamps for positions [a_r, b_r] should all be updated to r. Right after that, the desired answer of a query [l, r] is the number of positions whose timestamp is not smaller than l.

We would like to, for each r, keep the desired answer for every l. To achieve this, when we change the timestamps of k positions from r' to r, the answers for l in [r' + 1, r] should each be increased by k.

To do it fast, we can merge consecutive positions with the same timestamp into a segment, and use a balanced tree (e.g. std::set) to maintain the segments. O(1) new segments appear when adding an interval, and when a segment is completely covered by later intervals, it will be deleted. By amortized analysis, the total number of balanced tree operations and the number of range modifications of answers (see above) are both O(n). We spend time in this part.

Now we consider how to get the answer. It's obvious that we will select the k largest values. We can use binary search to find the minimum we finally select, i.e. we should, for several integers x, count how many values of [l, r] are not smaller than x and count the sum of these values by the way to get the answer.

For each i, we will select all [l, i]'s such that their interval of intervals values is not smaller than x. As the value of [l, r] is not smaller than [l + 1, r] or [l, r - 1], it's obvious that all l's smaller than an integer L_i will be taken and L_i + 1 will be not smaller than L_i. Now we can iterate i from 1 to n, maintaining the sum of values of [l, i] (1 ≤ l < L_i) and the value of [L_i, i] by maintaining the difference between the answers for l and l + 1 (in this way we carry out a range increment in O(1) time). Similar to the sliding-window method, we try to increase L_i when i changes to i + 1. Therefore, we spend O(n) time for each x we check with.

Summing everything up, the total time complexity of this problem is .

#include<bits/stdc++.h>
using namespace std;
#define MN 300000
#define p make_pair
#define pb push_back
#define A first
#define B second
set< pair<int,int> > st;
set< pair<int,int> >::iterator it,tt;
vector< pair<int,int> > v[MN+5];
int f[MN+5]; 
int main()
{
	int n,m,i,j,k,l,r,x,X,t2;long long s1,s2,S1,S2,t1;
	scanf("%d%d",&n,&m);
	st.insert(p(1,0));st.insert(p(1e9,0));
	for(i=1;i<=n;++i)
	{
		scanf("%d%d",&l,&r);
		tt=(it=st.upper_bound(p(l,n)))--;
		v[i].pb(p(x=it->B,it->A-tt->A));
		if(it->A<l)v[i].pb(p(x,l-it->A));
		else st.erase(it);
		v[i].pb(p(i,r-l));st.insert(p(l,i));
		while(tt->A<r)it=tt++,v[i].pb(p(x=it->B,it->A-tt->A)),st.erase(it);
		if(tt->A>r)v[i].pb(p(x,tt->A-r)),st.insert(p(r,x));
	}
	for(l=1,r=1e9;l<=r;)
	{
		x=l+r>>1;
		memset(f,0,sizeof(f));
		for(i=j=1,s1=s2=t1=t2=0;i<=n;++i)
		{
			for(k=0;k<v[i].size();++k)
				if(v[i][k].A<j)t1+=1LL*v[i][k].A*v[i][k].B;
				else t1+=1LL*(j-1)*v[i][k].B,t2+=v[i][k].B,f[v[i][k].A]+=v[i][k].B;
			while(j<=i&&t2>=x)t1+=t2,t2-=f[j++];
			s1+=t1;s2+=j-1;
		}
		if(s2>=m)X=x,S1=s1,S2=s2,l=x+1;else r=x-1;
	}
	printf("%lld",S1-(S2-m)*X);
}

If we only need to calculate (j|k = i), we can do these:

1. Let (j|i = i).

2. Let C_i = A_i·Bi, it can be found that (j|i = i).

3. So (j|i = i and j ≠ i).

To calculate A_i fast (B_i is the same), let f(x, i) be the sum of a_j which j|i = i and the lower x binary bits of j is equal to i's.

So f(n, i) = a_i, f(x - 1, i) = f(x, i) if i&2^x = 0 , f(x - 1, i) = f(x, i) + f(x, i - 2^x) if i&2^x = 2^x, and A_i = f(0, i).

We can calculate all A_i and B_i in O(n·2ⁿ) time.

Getting c_i from C_i is the inversion of getting A_i from a_i. So we can use f(x, i) once again. f(x, i) = f(x - 1, i) if i&2^x = 0, f(x, i) = f(x - 1, i) - f(x - 1, i - 2^x) if i&2^x = 2^x. So we can get all c_i in O(n·2ⁿ) total time.

But in this problem we need to calculate (j|k = i and j&k = 0).

In fact, there is a well-known algorithm for this problem.

The main idea of this algorithm is consider the number of "1" binary bits.

First, let BC(x) be the number of "1" binary bits in x.

Let (j|i = i and BC(j) = x).

Then we calculate (y + z = x), and (j|i = i and j ≠ i).

So (j|k = i and BC(j) + BC(k) = x).

Finally c_i we need to calculate is equal to c(BC(i), i), because if j|k = i and BC(j) + BC(k) = BC(i), j&k must be 0.

This algorithm cost O(n²·2ⁿ) time. Unfortunately, it may be too slow in this problem.

In this problem, we only need to calculate c_i&3, equal to c_i modulo 4.

In fact, when the answer is modulo p, an arbitrary integer, my solution works.

Let .

Then we calculate F_i = A_i·B_i, and (j|i = i and j ≠ i).

So (j|k = i).

If j|k = i, BC(j) + BC(k) ≥ BC(i). If j|k = i and j&k = 0, BC(j) + BC(k) = BC(i).

We find that , because if BC(j) + BC(k) > BC(i), a_j·b_k·p^{BC(j) + BC(k) - BC(i)} can be divided by p.

So the total time is O(n·2ⁿ).

A remainder problem is it can not be modulo p when calculating in this algorithm, so the number may be very large.

Fortunately, in this problem, p is only 4. We can use 128-bit integers or merge two 64-bit integers into one number when calculating.

But in fact, we only care modulo p, so we can let all number be modulo p^n + 1. Single 64-bit integer is enough.

#include<cstdio>
typedef long long ll;
#define MN (1<<21)
char A[MN+5],B[MN+5];
int s[MN+5];ll a[MN+5],b[MN+5];
int main()
{
	int n,i,j;
	scanf("%d%s%s",&n,A,B);
	for(i=0;i<1<<n;++i)s[i]=s[i>>1]+((i&1)<<1),a[i]=(ll)(A[i]-'0')<<s[i],b[i]=(ll)(B[i]-'0')<<s[i];
	for(i=0;i<n;++i)for(j=0;j<1<<n;++j)if(j&(1<<i))a[j]+=a[j^(1<<i)],b[j]+=b[j^(1<<i)];
	for(i=0;i<1<<n;++i)a[i]*=b[i];
	for(i=0;i<n;++i)for(j=0;j<1<<n;++j)if(j&(1<<i))a[j]-=a[j^(1<<i)];
	for(i=0;i<1<<n;++i)putchar(((a[i]>>s[i])&3)+'0');
}