阿里去要企业网站建设方案书,公司网站建设需要注意什么,wordpress 城市分类,泛华建设集团有限公司网站[CQOI2015]选数
推式子
根据题意可写出式子#xff1a; ∑a1LH∑a2LH⋯∑anLH[gcd(a1,a2…an)k]∑a1⌈Lk⌉⌊Hk⌋∑a2⌈Lk⌉⌊Hk⌋⋯∑an⌈Lk⌉⌊Hk⌋[gcd(a1,a2…an)k]∑k1⌊Hk⌋μ(k)(⌊Hkd⌋−⌈Lkd⌉1)n提前处理一下左右端点∑k1⌊Hk⌋μ(k)(⌊Hkd⌋−⌊L−1kd⌋)n\sum_…[CQOI2015]选数
推式子
根据题意可写出式子 ∑a1LH∑a2LH⋯∑anLH[gcd(a1,a2…an)k]∑a1⌈Lk⌉⌊Hk⌋∑a2⌈Lk⌉⌊Hk⌋⋯∑an⌈Lk⌉⌊Hk⌋[gcd(a1,a2…an)k]∑k1⌊Hk⌋μ(k)(⌊Hkd⌋−⌈Lkd⌉1)n提前处理一下左右端点∑k1⌊Hk⌋μ(k)(⌊Hkd⌋−⌊L−1kd⌋)n\sum_{a_1 L} ^{H} \sum_{a_2 L} ^{H} \dots \sum_{a_n L} ^{H}[gcd(a_1, a_2 \dots a_n) k]\\ \sum_{a_1 \lceil \frac{L}{k} \rceil} ^{\lfloor \frac{H}{k} \rfloor} \sum_{a_2 \lceil \frac{L}{k} \rceil} ^{\lfloor \frac{H}{k} \rfloor}\dots \sum_{a_n \lceil \frac{L}{k} \rceil} ^{\lfloor \frac{H}{k} \rfloor}[gcd(a_1, a_2 \dots a_n) k]\\ \sum_{k 1} ^{\lfloor \frac{H}{k} \rfloor} \mu(k) \left( \lfloor \frac{H}{kd} \rfloor - \lceil \frac{L}{kd} \rceil 1 \right) ^n\\ 提前处理一下左右端点\\ \sum_{k 1} ^{\lfloor \frac{H}{k} \rfloor} \mu(k) \left( \lfloor \frac{H}{kd} \rfloor - \lfloor \frac{L - 1}{kd} \rfloor\right) ^n\\ a1L∑Ha2L∑H⋯anL∑H[gcd(a1,a2…an)k]a1⌈kL⌉∑⌊kH⌋a2⌈kL⌉∑⌊kH⌋⋯an⌈kL⌉∑⌊kH⌋[gcd(a1,a2…an)k]k1∑⌊kH⌋μ(k)(⌊kdH⌋−⌈kdL⌉1)n提前处理一下左右端点k1∑⌊kH⌋μ(k)(⌊kdH⌋−⌊kdL−1⌋)n 非常简单的反演公式所以我们只要按照这个公式套上杜教筛就行了。
代码
/*Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include bits/stdc.h#define mp make_pair
#define pb push_back
#define endl \n
#define mid (l r 1)
#define lson rt 1, l, mid
#define rson rt 1 | 1, mid 1, r
#define ls rt 1
#define rs rt 1 | 1using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int pii;const double pi acos(-1.0);
const double eps 1e-7;
const int inf 0x3f3f3f3f;inline ll read() {ll f 1, x 0;char c getchar();while(c 0 || c 9) {if(c -) f -1;c getchar();}while(c 0 c 9) {x (x 1) (x 3) (c ^ 48);c getchar();}return f * x;
}const int N 1e6 10, mod 1e9 7;int prime[N], mu[N], cnt;
ll n, k, L, H;bool st[N];void init() {mu[1] 1;for(int i 2; i N; i) {if(!st[i]) {prime[cnt] i;mu[i] -1;}for(int j 0; j cnt i * prime[j] N; j) {st[i * prime[j]] 1;if(i % prime[j] 0) break;mu[i * prime[j]] -mu[i];}}for(int i 1; i N; i) {mu[i] mu[i - 1];}
}ll quick_pow(ll a, ll n) {ll ans 1;while(n) {if(n 1) ans ans * a % mod;a a * a % mod;n 1;}return ans;
}mapll, ll ans_s;ll S(ll n) {if(n N) return mu[n];if(ans_s.count(n)) return ans_s[n];ll ans 1;for(ll l 2, r; l n; l r 1) {r n / (n / l);ans ((ans - (r - l 1) * S(n / l) % mod) % mod mod) % mod;}return ans_s[n] ans;
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);init();n read(), k read(), L read(), H read();ll ans 0;L (L - 1) / k, H H / k;for(ll l 1, r; l H; l r 1) {r min( L / l ? L / (L / l) : inf , H / (H / l));ans (ans 1ll * (((S(r) - S(l - 1)) % mod mod) % mod) * quick_pow((H / l) - (L / l), n) % mod) % mod;}cout ans endl;return 0;
}
