\u9898\u76ee\u7565<\/p>\n
\u9898\u76ee\u6c42\u7684\u5c31\u662f\u4e2a$$\\sum\\text{\u8f6e\u6570}$$ \u6240\u4ee5\u6839\u672c\u4e0d\u7528\u7ba1\u4e0b\u9762\u90a3\u4e2a\u63d0\u793a<\/p>\n
\u6839\u636e\u9898\u610f\u50cf\u7d20\u6570\u7b5b\u4e00\u6837\u5728$$[L,R]$$\u4e2d\u9009\u62e9\u5fc5\u987b\u9009\u62e9\u7684\u6570\uff0c\u7b5b\u6389\u5269\u4e0b\u7684\u6570(\u8fd9\u4e9b\u6570\u7684\u500d\u6570)<\/p>\n
\u8bb0\u5fc5\u987b\u9009\u62e9\u7684\u6570\u4e3a$$sum$$,\u5219\u4ee4$$f[i]=sum * C(n – sum,n-i) * (i – 1)! * (n – i)!$$<\/p>\n
\u5219$$ans = \\displaystyle\\sum_{i = sum}^ni * f[i] = \\displaystyle\\sum_{i=sum}^nsum * C(n – sum,n-i)*i! *(n-i)$$<\/p>\n
$$ans = \\displaystyle\\sum_{i=sum}^n sum * \\frac{(n – sum)!}{(n – i)!(i-sum)} *i!$$<\/p>\n
#include <iostream>\n#include <algorithm>\n#include <array>\n\nusing namespace std;\nusing ll = long long;\nconst int maxn = 1e7 + 1e2;\nconst int mod = 1e9 + 7;\narray<int, maxn> fac, inv;\narray<bool, maxn> vis;\nint l, r, n;\n\nint qpow(int x, int y) {\n int res = 1;\n for (; y; y >>= 1, x = 1ll * x * x % mod) {\n if (y & 1) res = 1ll * res * x % mod;\n }\n return res;\n}\n\nvoid shai() {\n fac[0] = 1;\n for (int i = 1; i <= r; ++i) {\n fac[i] = 1ll * i * fac[i - 1] % mod;\n }\n inv[r] = qpow(fac[r], mod - 2);\n for (int i = r; i; --i)inv[i - 1] = 1ll * i * inv[i] % mod;\n}\n\nint main() {\n ios::sync_with_stdio(false);\n cin.tie(0);\n cout.tie(0);\n cin >> l >> r;\n shai();\n\n int sum = 0;\n for (int i = l; i <= r; ++i) {\n if (!vis[i]) {\n ++sum;\n for (int j = i << 1; j <= r; j += i)vis[j] = true;\n }\n }\n n = r - l + 1;\n int ans = 0;\n for (int i = sum; i <= n; ++i) {\n ans = (ans + 1ll * sum * fac[n - sum] % mod * inv[i - sum] % mod * fac[i] % mod) % mod;\n }\n cout << ans << \"\\n\";\n\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"UPC 6887 \u6e38\u620f \u9898\u76ee\u7565 \u9898\u76ee\u6c42\u7684\u5c31\u662f\u4e2a$$\\sum\\text{\u8f6e\u6570}$$ \u6240\u4ee5\u6839\u672c\u4e0d\u7528\u7ba1\u4e0b\u9762\u90a3\u4e2a\u63d0\u793a […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false},"categories":[43,44,22],"tags":[],"class_list":["post-344","post","type-post","status-publish","format-standard","hentry","category-43","category-44","category-22"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-5y","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/344","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=344"}],"version-history":[{"count":2,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/344\/revisions"}],"predecessor-version":[{"id":346,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/344\/revisions\/346"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=344"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=344"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=344"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}