제출 #9135

#제출 시각아이디문제언어결과실행 시간메모리
9135aintaActual visible points (kriii2_AC)C++98
0 / 4
192 ms6292 KiB
#pragma warning(disable:4996) #include<stdio.h> #include<algorithm> using namespace std; int n, m, w[101000]; long long Mod = 1000000007, F[201000], G[201000], Res, invF[201000]; bool chk[101000]; long long Inv(long long a){ long long cnt = Mod - 2, r = 1; while (cnt){ if (cnt % 2){ r = r*a%Mod; } cnt /= 2; a = a*a%Mod; } return r; } long long Gap(int a){ if (a == 0)return 0; return F[a + n - 1] * invF[n] % Mod * invF[a - 1] % Mod; } void Do(int a){ G[a] = (G[a] + Gap(a) - Gap(a-1) + Mod) % Mod; int i, ck = chk[a]; for (i = a * 2; i <= 100000; i += a){ G[i] = (G[i] + Mod - G[a]) % Mod; if (chk[i])ck = true; } if (ck)Res = (Res + G[a]) % Mod; } int main() { int i; scanf("%d%d", &n, &m); for (i = 1; i <= m; i++){ scanf("%d", &w[i]); chk[w[i]] = true; } F[0] = 1; for (i = 1; i <= 200010; i++){ F[i] = F[i - 1] * i%Mod; invF[i] = Inv(i); } for (i = 1; i <= 100000; i++){ Do(i); } printf("%lld\n", Res); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...