2013
12-21

# Frobenius

The Frobenius problem is an old problem in mathematics, named after the German mathematician G. Frobenius (1849�1917).Let a1, a2, …, an be integers larger than 1, with greatest common divisor (gcd) 1. Then it is known that there are finitely many integers larger than or equal to 0, that cannot be expressed as a linear combination w1a1 + w2a2 + … + wnan using integer coefficients wi ≥ 0. The largest of such nonnegative integers is known as the Frobenius number of a1, a2, …, an (denoted by F(a1, a2, …, an)). So: F(a1, a2, …, an) is the largest nonnegative integer that cannot be expressed as a nonnegative integer linear combination of a1, a2, …, an.

For n = 2 there is a simple formula for F(a1, a2). However, for n ≥ 3 it is much more complicated. For n = 3 only for some special choices of a1, a2, a3 formulas exist. For n > 4 no formulas are known at all.

We will consider here the Frobenius problem for n = 4. In this case our version of the problem can be formulated as follows. Let four integers a, b, c and d be given, with a, b, c, d > 1 and gcd(a, b, c, d) = 1. We want to know two things.

How many nonnegative integers less than or equal to 1,000,000 cannot be expressed as a nonnegative integer linear combination of the values a, b, c and d?
Is the Frobenius number of a, b, c and d less than or equal to 1,000,000 and if so, what is its value?

The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:One line, containing four integers a, b, c, d (with 1 < a, b, c, d ≤ 10, 000 and gcd(a, b, c, d) = 1), separated by single spaces.

For every test case in the input file, the output should contain two lines.The first line contains the number of integers between 0 and 1,000,000 (boundaries included) that cannot be expressed as a*w + b*x + c*y + d*z, where w, x, y, z are nonnegative (meaning ≥ 0) integers.
The second line contains the Frobenius number if this is less than or equal to 1,000,000 and otherwise &#8722;1, meaning that the Frobenius number of a, b, c and d is larger than 1,000,000.

3
8 5 9 7
5 8 5 5
1938 1939 1940 1937

6
11
14
27
600366
-1

code：

#include<stdio.h>
#include<string.h>
bool f[10001],ff[1010001];
int a[5];
int main()
{
int i,j,k,max,cas,t,x,count,flag;
scanf("%d",&cas);
while(cas--)
{
memset(f,0,sizeof(f));
k=0;
for(i=1;i<=4;i++)
{
scanf("%d",&x);
if(f[x]==0) {a[++k]=x;f[x]=1;}
}
/*
for(i=1;i<=k;i++)
printf("%d ",a[i]);
printf("\n\n");
*/
memset(ff,0,sizeof(ff));
ff[0]=1;count=1;max=0;
for(i=1;i<=1000000;i++)
{
flag=0;
for(j=1;j<=k;j++)
{
if(i-a[j]>=0&&ff[i-a[j]]==1)
{ff[i]=1;count++;flag=1;break;}
}
if(flag==0) {max=i;/*printf("%d\n",i);*/}
}

t=0;
for(i=1000000+1;i<=1010000;i++)
{
flag=0;
for(j=1;j<=k;j++)
if(i-a[j]>=0&&ff[i-a[j]]) {flag=1;ff[i]=1;break;}
if(flag==0)
{t=1;break;}
}
if(t) printf("%d\n-1\n",1000001-count);
else printf("%d\n%d\n",1000001-count,max);
}
}
/*
300
8 5 9 7
5 8 5 5
1938 1939 1940 1937
*/

1. 被仇恨蒙蔽了双眼？笑死我了，日本人每年都举行荷包纪念日活动，还邀请一些国家参加，告诉他们日本是战争的受害者，被爆了多可怜云云，你知道为什么“另一些国家”不参加么？“被仇恨蒙蔽了双眼”？不是，因为他们发现日本在外交场合只是说自己被爆了多可怜，却从不说他们为

2. 被仇恨蒙蔽了双眼？笑死我了，日本人每年都举行荷包纪念日活动，还邀请一些国家参加，告诉他们日本是战争的受害者，被爆了多可怜云云，你知道为什么“另一些国家”不参加么？“被仇恨蒙蔽了双眼”？不是，因为他们发现日本在外交场合只是说自己被爆了多可怜，却从不说他们为

3. 被仇恨蒙蔽了双眼？笑死我了，日本人每年都举行荷包纪念日活动，还邀请一些国家参加，告诉他们日本是战争的受害者，被爆了多可怜云云，你知道为什么“另一些国家”不参加么？“被仇恨蒙蔽了双眼”？不是，因为他们发现日本在外交场合只是说自己被爆了多可怜，却从不说他们为

4. 被仇恨蒙蔽了双眼？笑死我了，日本人每年都举行荷包纪念日活动，还邀请一些国家参加，告诉他们日本是战争的受害者，被爆了多可怜云云，你知道为什么“另一些国家”不参加么？“被仇恨蒙蔽了双眼”？不是，因为他们发现日本在外交场合只是说自己被爆了多可怜，却从不说他们为

5. 被仇恨蒙蔽了双眼？笑死我了，日本人每年都举行荷包纪念日活动，还邀请一些国家参加，告诉他们日本是战争的受害者，被爆了多可怜云云，你知道为什么“另一些国家”不参加么？“被仇恨蒙蔽了双眼”？不是，因为他们发现日本在外交场合只是说自己被爆了多可怜，却从不说他们为

6. 被仇恨蒙蔽了双眼？笑死我了，日本人每年都举行荷包纪念日活动，还邀请一些国家参加，告诉他们日本是战争的受害者，被爆了多可怜云云，你知道为什么“另一些国家”不参加么？“被仇恨蒙蔽了双眼”？不是，因为他们发现日本在外交场合只是说自己被爆了多可怜，却从不说他们为

7. 被仇恨蒙蔽了双眼？笑死我了，日本人每年都举行荷包纪念日活动，还邀请一些国家参加，告诉他们日本是战争的受害者，被爆了多可怜云云，你知道为什么“另一些国家”不参加么？“被仇恨蒙蔽了双眼”？不是，因为他们发现日本在外交场合只是说自己被爆了多可怜，却从不说他们为