The Flower Garden
时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte
总提交:481 测试通过:290
描述
Imagine Betsy's surprise as she rounded the barn and discovered that Farmer John had built a secret greenhouse that was now brimming with gorgeous flowers. Her mind ran wild as visions of a gorgeous
colorful garden swirled through her little bovine brain.
"I think I'll make a long row of F (7 <= F <= 10,000) flowers against the far fence," she thought. "I'll plant roses in every 3rd slot, begonias in every 7th slot that is still open, and daisies in every
4th slot that is still open." Betsy wondered how many open slots would remain. She realized that the number would depend on which slot she started planting when she intended to fill every Nth slot
with a kind of flower.
Help Betsy know how many open slots will remain. Read a set of K (1 <= K <= 100) planting descriptors, each of which tells a starting location L (1 <= L <= F) -- L=1 is the first flower -- and an
interval I (1 <= I <= F) for planting flowers. Deduce the number of empty slots that remain after planting the entire set.
If Betsy followed through on her initial vision, she might specify the planting as:
30 3 [30 slots total; 3 kinds of flowers]
1 3 [start at slot 1 and plant roses every 3rd slot]
3 7 [start at slot 3 and plant begonias every 7rd slot]
1 4 [start at slot 1 and plant daisies in every 4th slot]
Thus, the empty garden looks like this:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Then, after the rose planting:
R . . R . . R . . R . . R . . R . . R . . R . . R . . R . .
Then, after the begonia planting:
R . B R . . R . . R . . R . . R B . R . . R . B R . . R . .
Then, after the daisy planting:
R . B R D . R . D R . . R . . R B . R . D R . B R . . R D .
13 empty slots remain after all the planting.
输入
* Line 1: Two space-separated integers: F and K
* Lines 2..K+1: Line j contains two space-separated integers that specify the planting of one kind of flower: L_j and I_j
输出
* Line 1: A single line with a single integer that is the number of empty flower slots that remain after the planting is complete
样例输入
30 3
1 3
3 7
1 4
样例输出
13
题目来源
Elite 2007 US Open Competition
分析：只能说这道题不好了，开始想到剩余定理，最小公倍数，但感觉都不简单，后来试试硬着算下试试。结果。。。。。AC了。
#include <stdio.h>
int main()
{
int n,k,l,i,j,m,f;
int ff[10000]={0},kk[100][2];
scanf("%d%d",&n,&k);
for (i=0;i<k;i++)
{
scanf("%d%d",&kk[i][0],&kk[i][1]);
}
for (i=0;i<k;i++)
{
for (j=kk[i][0]-1;j<n;j+=kk[i][1])
{
ff[j]=1;
}
}
m=0;
for (i=0;i<n;i++)
{
if (ff[i]==0)
{
m++;
}
}
printf("%d\n",m);
}