[信息与未来 2015] 买木头

Luogu
IDLGB3880
Time1000ms
Memory128MB
DifficultyP2
2015二分江苏信息与未来
有 $n$ 个木材供应商,每个供应商有长度相同的一定数量的木头。长木头可以锯短,但短木头不能接长。有一个客人要求 $m$ 根长度相同的木头,要求计算出:此时供货商提供的木头满足客人要求的最大长度是多少。 例如 $n=2,m=30$,两个供货商的木头为: - $12,10$(第 $1$ 个供货商的木头长度为 $12$,共有 $10$ 根); - $5,10$(第 $2$ 个供货商的木头长度为 $5$,共有 $10$ 根)。 计算的结果为 $5$,即长度为 $12$ 的木头一根可锯出两根长度为 $5$ 的木头,多余的无用;长度为 $5$ 的木头不动,此时,可以得到 $30$ 根长度为 $5$ 的木头。 ## Input 一行四个整数 $n,m,l_1,s_1$。其中 $l_1$ 是第一个供货商木头的长度,$s_1$ 是第一个供货商木头的数量。其他供货商木头 的长度和数量 $l_i$ 和 $s_i(i\ge2)$由下面的公式给出: - $l_i=((l_{i-1}\times37011+10193) \bmod 10000)+1$; - $s_i=((s_{i-1}\times73011+24793) \bmod 100)+1$。 ## Output 一个整数,即满足要求的 $m$ 根长度相同的木头的最大长度。 [samples] ## Note $1\le n\le10^4,1\le m\le10^6,1\le l_1\le10^4, 1\le s_1\le100$。
Samples
Input #1
10 10000 8 20
Output #1
201
API Response (JSON)
{
  "problem": {
    "name": "[信息与未来 2015] 买木头",
    "description": {
      "content": "有 $n$ 个木材供应商,每个供应商有长度相同的一定数量的木头。长木头可以锯短,但短木头不能接长。有一个客人要求 $m$ 根长度相同的木头,要求计算出:此时供货商提供的木头满足客人要求的最大长度是多少。 例如 $n=2,m=30$,两个供货商的木头为: - $12,10$(第 $1$ 个供货商的木头长度为 $12$,共有 $10$ 根); - $5,10$(第 $2$ 个供货商的木头长度为 $5",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3880"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 个木材供应商,每个供应商有长度相同的一定数量的木头。长木头可以锯短,但短木头不能接长。有一个客人要求 $m$ 根长度相同的木头,要求计算出:此时供货商提供的木头满足客人要求的最大长度是多少。\n\n例如 $n=2,m=30$,两个供货商的木头为:\n- $12,10$(第 $1$ 个供货商的木头长度为 $12$,共有 $10$ 根);\n- $5,10$(第 $2$ 个供货商的木头长度为 $5...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments