题目

输入格式

第一行，两个正整数 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 = \sum\limits_{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
    
     #include
     
      #include
      
       #include
       
        #include
        
         #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<
         
          <<' '; 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\n",ans); } return 0;}