Educational Codeforces Round 37-G.List Of Integers题解
一、题目
二、题目链接
http://codeforces.com/contest/920/problem/G
三、题意
给定一个$t$,表示有t次查询。每次查询给定一个$x$, $p$, $k$,需要输出一个大于$x$、与$p$互质、第$k$大的数字。如样例1所示,比$7$大、与$22$互质、第$1$大的数字是$9$,第$2$大的数字是$13$,第$3$大的数字是$15$。
四、思路
二分+容斥原理。
二分一个数字$mid$,看看$[x+1,mid]$之间与$p$互质的数的个数。需要注意的是,如果个数是$k$,还要判断二分的$mid$是不是与$p$互质。如果是,说明要输出的值在$[x+1, mid)$之间,要需要继续做二分。(注意括号样式哦)
统计$[x+1, mid]$之间与$p$互质的数的个数,方法是:把这个区间内$p$的素因子的倍数全部筛掉,剩余的就是与$p$互质的了。在筛的过程中,比如$p$是$12$,素因子是$2$、$3$,筛掉$2$的倍数的方法是:区间长度$len - (mid / 2 - x / 2)$。同理,筛掉$3$的倍数的方法也一样。但是,对于所有$6$的倍数,会被减两次,所以,需要再加一次。而这个过程,其实就是容斥原理。
在这个题目中,利用容斥原理统计个数时,有两个写法:
1、每次二分一个上界值$mid$,就枚举二进制;
2、保存所有的询问,对每个询问的$p$,都预处理出它的所有素因子组合的乘积。然后,再枚举每一个询问,传入二分上界值$mid$时,枚举预处理的$p$的所有素因子组 合的乘积即可。(详细的写法可参考源代码)
另外,还有一点,在做询问之前,需要预处理出$[1, 1e6]$区间内所有数字的素因子。
五、源代码
1、写法一:每次二分一个上界值$mid$,就枚举二进制;
#pragma GCC optimize(2) #pragma comment(linker, "/STACK:102400000, 102400000") #include<bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 1e6 + 10; template <class T> inline void read(T &x) { int t; bool flag = false; while((t = getchar()) != '-' && (t < '0' || t > '9')) ; if(t == '-') flag = true, t = getchar(); x = t - '0'; while((t = getchar()) >= '0' && t <= '9') x = x * 10 + t - '0'; if(flag) x = -x; } bool prime[MAXN]; vector<LL> d[MAXN];//d[i]:数字i的所有素因子 void init() { const int N = 1000000; for(int i = 0; i <= N; ++i)d[i].clear(), prime[i] = true; for(int i = 2; i <= N; ++i) { if(prime[i]) { for(int j = i + i; j <= N; j += i)prime[j] = false; } } for(int i = 2; i <= N; ++i) { if(prime[i]) { for(int j = i; j <= N; j += i)d[j].push_back(LL(i)); } } } /**[x+1, mid]**/ LL calc(LL x, LL p, LL mid) { LL res = mid - x; /*枚举二进制: 如果i=5,二进制为0101,从低位数起,第0位和第2位为1, 那么就取d[p]的第0个和第2个素因子,计算乘积,去做容斥操作。 同时,需要统计取得素因子的个数。 如果是奇数,那么,容斥操作中符号是+,否则是-。 */ for(int i = 1, t = 1 << d[p].size(); i < t; ++i) { LL cnt = 0, prod = 1; for(int j = i, k = 0; j > 0; j >>= 1, ++k) { if(j & 1) { cnt++; prod *= d[p][k]; } } res -= (mid / prod - x / prod) * (cnt % 2 == 1 ? 1 : -1); } return res; } int main() { #ifndef ONLINE_JUDGE freopen("Ginput.txt", "r", stdin); #endif // ONLINE_JUDGE LL T, x, p, k, low, high, mid, ans = 0, tmp; init(); read(T); while(T--) { read(x), read(p), read(k); low = x, high = 1LL << 25;/*这个地方要特别注意,写大了就超时。*/ while(low < high - 1) { mid = (low + high) / 2; tmp = calc(x, p, mid); if(tmp < k)low = mid; else if(tmp > k)high = mid; else { if(__gcd(mid, p) > 1LL)high = mid; else { ans = mid; break; } } } printf("%lld\n", ans); } return 0; }
2、保存所有的询问,对每个询问的$p$,都预处理出它的所有素因子组合的乘积。然后,再枚举每一个询问,传入二分上界值$mid$时,枚举预处理的$p$的所有素因子组 合的乘积;
#pragma GCC optimize(2) #pragma comment(linker, "/STACK:102400000, 102400000") #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef tuple<LL, LL, LL> T3L; typedef pair<LL, LL> P2L; const int MAXN = 1e6 + 10; template <class T> inline void read(T &x) { int t; bool flag = false; while((t = getchar()) != '-' && (t < '0' || t > '9')) ; if(t == '-') flag = true, t = getchar(); x = t - '0'; while((t = getchar()) >= '0' && t <= '9') x = x * 10 + t - '0'; if(flag) x = -x; } bool prime[MAXN]; vector<LL> d[MAXN];/*d[i]:数字i的素因子*/ vector<P2L> f[MAXN];/*f[i]:数字i的素因子组合的乘积和该组合的素因子个数*/ vector<T3L> qs; void init() { const int N = 1000000; qs.clear(); for(int i = 0; i <= N; ++i)d[i].clear(), f[i].clear(), prime[i] = true; for(int i = 2; i <= N; ++i) { if(prime[i]) { for(int j = i + i; j <= N; j += i)prime[j] = false; } } for(int i = 2; i <= N; ++i) { if(prime[i]) { for(int j = i; j <= N; j += i)d[j].push_back(LL(i)); } } } /**[x+1, mid]**/ LL calc(LL x, LL p, LL mid) { LL res = mid - x; for(int i = 0; i < f[p].size(); ++i) {/*直接枚举素因子组合的乘积*/ LL prod = f[p][i].first, cnt = f[p][i].second; res -= (mid / prod - x / prod) * (cnt % 2 == 1 ? 1 : -1); } return res; } int main() { #ifndef ONLINE_JUDGE freopen("Ginput.txt", "r", stdin); #endif // ONLINE_JUDGE LL T, x, p, k, low, high, mid, ans = 0, tmp; init(); read(T); for(int i = 0; i < T; ++i) { read(x), read(p), read(k); qs.push_back(make_tuple(x, p, k));/*保存所有询问*/ } /*预处理每个询问的p的素因子组合的乘积、组合个数。 写法同方法1。 */ for(int t = 0; t < T; ++t) { tmp = get<1>(qs[t]); if(f[tmp].size() == 0) { for(int i = 1, top = 1 << d[tmp].size(); i < top; ++i) { LL cnt = 0, prod = 1; for(int j = i, k = 0; j > 0; j >>= 1, ++k) { if(j & 1) { cnt++; prod *= d[tmp][k]; } } f[tmp].push_back(make_pair(prod, cnt)); } } } for(int t = 0; t < T; ++t) { x = get<0>(qs[t]), p = get<1>(qs[t]), k = get<2>(qs[t]); low = x, high = 1LL << 25;/*这个地方要特别注意,写大了就超时。*/ while(low < high - 1) { mid = (low + high) / 2; tmp = calc(x, p, mid); if(tmp < k)low = mid; else if(tmp > k)high = mid; else { if(__gcd(mid, p) > 1LL)high = mid; else { ans = mid; break; } } } printf("%lld\n", ans); } return 0; }