做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2933. -- 「一本通 6.6 练习 2」方程的解

2933: 「一本通 6.6 练习 2」方程的解

时间限制: 1 Sec  内存限制: 512 MB
提交: 0  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

佳佳碰到了一个难题,请你来帮忙解决。对于不定方程 a1+a2+⋯+ak−1+ak=g(x)a_1+a_2+cdots +a_{k-1}+a_k=g(x)a1+a2++ak1+ak=g(x),其中 k≥2kge 2k2k∈N∗kin mathbb{N}^*kNxxx 是正整数,g(x)=xxmod1000(即 xxx^xxx 除以 100010001000 的余数),x,kx,kx,k 是给定的数。我们要求的是这个不定方程的正整数解组数。

举例来说,当 k=3,x=2k=3,x=2k=3,x=2 时,方程的解分别为:

a1=1a2=1a3=2    a1=1a2=2a3=1    a1=2a2=1a3=1

输入

有且只有一行,为用空格隔开的两个正整数,依次为 k,xk,xk,x

输出

有且只有一行,为方程的正整数解组数。

提示

样例输入

3 2

样例输出

3

对于 40%40\%40% 数据,答案不超过 101610^{16}1016
对于全部数据,1≤k≤100,1≤x<231,k≤g(x)1le kle 100,1le xlt 2^{31},kle g(x)1k100,1x<231,kg(x)

标签

[上一题][提交][讨论版][状态][下一题]