#P2371. [国家集训队] 墨墨的等式
[国家集训队] 墨墨的等式
题目描述
墨墨突然对等式很感兴趣,他正在研究 存在非负整数解的条件,他要求你编写一个程序,给定 ,求出有多少 可以使等式存在非负整数解。
输入格式
第一行三个整数 。
第二行 个整数 。
输出格式
一行一个整数,表示有多少 可以使等式存在非负整数解。
2 5 10
3 5
5
提示
对于 的数据,,。
对于 的数据,,。
对于 的数据,,,。
墨墨突然对等式很感兴趣,他正在研究 ∑i=1naixi=b 存在非负整数解的条件,他要求你编写一个程序,给定 n,a1…n,l,r,求出有多少 b∈[l,r] 可以使等式存在非负整数解。
第一行三个整数 n,l,r。
第二行 n 个整数 a1…n。
一行一个整数,表示有多少 b∈[l,r] 可以使等式存在非负整数解。
2 5 10
3 5
5
对于 20% 的数据,n≤5,r≤10。
对于 40% 的数据,n≤10,r≤106。
对于 100% 的数据,n≤12,0≤ai≤5×105,1≤l≤r≤1012。