题目
输入格式
第一行，两个正整数 S 和 q，q 表示询问数量。
接下来 q 行，每行一个正整数 n。
输出格式
输出共 q 行，分别为每个询问的答案。
输入样例
30 3
9
29
1000000000000000000
输出样例
0
9
450000036
提示
对于100%的数据，2<=S<=2*10^6,1<=n<=10^18,1<=q<=10^5
题解
DZY系列多神题
容易知道(S)所有质因子的指数最大为(1)，否则结果都为(0)
如果满足，由(S)的范围可知其质因子最多有(7)个
那么(n = sumlimits_{i = 1}^{k} p_i * t_i)
(t_i)表示第(i)个质因子选了几个
很像一个背包，但是(n)很大，考虑转化
我们先将(n)减去所有(p_i)，保证至少选了一个
因为(p_i)是(S)的因子，所以可以写成(p_i * t_i = Sx + p_iy)且([p_iy < S])
也就是分成若干个(S)和剩余不足(S)的部分
那么最终的(n)一定是由若干个前面部分的(S)和后面部分的(p_iy)相加而得
由于任意的(p_iy < S)，所以(sum p_iy < k * S)，如果做背包，状态数为(k^2 * S approx 10^8)
可以吧，做一个(O(k * kS))的多重背包
看起来很汗，但可以跑过
至于这个多重背包的求法，就用一个类似滑动窗口的方法就可以实现(O(k * kS))了
然后对于每个(n)，枚举多出来的部分(n mod S + i * S)，(0 le i < 7)
除了后面多出来的，前面的若干(S)要分配给那些质因子，用组合数挡板法即可
就可以(O(7p))询问了
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000,P = 1e9 + 7;
inline LL read(){
LL out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int f[15000000],g[15000000],inv[10];
int S,p[maxn],pi,sum;
LL N;
bool Sp(){
int x = S;
for (int i = 2; i * i <= x; i++)
if (x % i == 0){
int cnt = 0;
p[++pi] = i; sum += i;
while (x % i == 0) x /= i,cnt++;
if (cnt > 1) return true;
}
if (x - 1) p[++pi] = x,sum += x;
return false;
}
bool init(){
if (Sp()) return true;
f[0] = 1;
int M = pi * S;
for (int i = 1; i <= pi; i++){
memcpy(g,f,sizeof(f));
for (int j = 0; j < p[i]; j++)
{
LL w = 0;
for (int k = j; k <= M; k += p[i])
{
w = (w + g[k]) % P;
if (k - S >= 0) w = ((w - g[k - S]) % P + P) % P;
f[k] = w;
}
}
}
inv[0] = inv[1] = 1;
for (int i = 2; i < 10; i++) inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
return false;
}
int cal(LL x,int y){
LL n = x + y - 1,m = y - 1;
int re = 1;
for (int i = 1; i <= m; i++)
re = 1ll * re * ((n - i + 1) % P) % P * inv[i] % P;
return re;
}
int main(){
S = read(); int T = read();
if (init()){
while (T--) puts("0");
return 0;
}
while (T--){
N = read();
N -= sum;
if (N < 0){puts("0"); continue;}
LL ans = 0,cnt = N / S;
for (int i = 0; i < pi && i <= cnt; i++)
ans = (ans + 1ll * f[N % S + i * S] * cal(cnt - i,pi) % P) % P;
printf("%lld
",ans);
}
return 0;
}