B.Basic Gcd Problem
题意：
$$
f_c(x)=\underset{i=1..x-1}{\max}c\cdot f_cgcd\left( i,x \right)\quad x>1
$$
$$
f_c\left( x \right) =1\quad \quad x=1
$$
给定\left( ni,ci \right) \quad求f_{c_i}\left( n_i \right) \text{mod}\left( 10^9+7 \right)
题解：
考虑c的贡献次数，我们最后的答案肯定是：c^{cnt} 形式，所以我们只需求出cnt。
当n=16,c=5时
显然f_c(16)=c\times {f_c(i)},i\in{1,2,4,8}
f_c(1)=1
f_c(2)=c\times max{f_c(i)},i\in{1}\rightarrow f_c(2)=c
f_c(4)=c\times max{f_c(i)},i\in{1,2}\rightarrow f_c(4)=c^2
f_c(8)=c\times max{f_c(i)},i\in{1,2,4}\rightarrow f_c(8)=c^3
所以f_c(16)=c^4,cnt=4
可以发现，cnt跟因数有关系
要让cnt尽可能大，我们需要尽可能多的相乘转换。
n=16=2^4
1\times2=2,2\times2=4,4\times2=8,8\times2=16
再如：
n=60
60=2^2\times3\times5
1\times2=2,2\times2=4,4\times3=12,12\times5=60
显然按照质因数分解后的个数依次相乘cnt是最大的。
答案就是质因数个数之和。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rd(a) scanf("%d", &a)
const ll mod = 1e9+7;
int n, c, T;
void solve()
{
ll ans = 1;
for(int i = 2; i <= n / i; i ++){
while(n % i == 0){
n /= i;
ans = ans * c % mod;
}
}
if(n != 1) ans = ans * c % mod;
printf("%lld\n", ans);
}
int main(){
rd(T);
while(T --){
rd(n),rd(c);
solve();
}
return 0;
}
F.Finding the Order
题意：
有两条平行线，ab与cd，通过ac，ad，bc，bd的长度来判断到底是ab//cd，还是ab//dc。
题解:
签到题，利用三角形两边之和大于第三边的原理，图中四个点构成中间两个三角形ACD和BCD,判断AD+BC和AC+BD的大小即可。
代码：
#include <bits/stdc++.h>
using namespace std;
#define rd(a) scanf("%d", &a)
int a, b, c, d;
void solve()
{
if(a+d<c+b) puts("AB//CD");
else puts("AB//DC");
}
int main(){
int T;
rd(T);
while(T --){
rd(a), rd(b), rd(c), rd(d);
solve();
}
return 0;
}
H.Harder Gcd Problem
题意：
给出一个集合的大小n，构造两个一样的集合A和B，分别包含{1,2,...,n}。
对两个集合中的不同数两两组合，每一对$gcd(A{pi},B{qi})>1$，求最多有多少对。
题解：
1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\ 11\ 12\ 13\ 14\ 15
7\ 14
5\ 15
3\ 6
9\ 12
2\ 4
8\ 10
如果要gcd>1那么对于每一个质数，所选的数必须为它的倍数。
如果存在质数x的倍数有偶数个，则可以完美匹配。
对于每个质数x，如2和7，2比7容易利用，我们先把7符合的剔除，再寻找2符合的。
如果存在质数x的倍数有奇数个,那么我们选择x的倍数中第二小的。因为质数本身为第一小，此时不选，以后没机会选了，如果选的太大，之后也没机会选。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mem(a, b) memset(a, b, sizeof(a))
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define pb push_back
#define MP make_pair
#define fi first
#define se second
const int maxn = 2e5 + 10;
int n, cnt, T;
int prime[maxn];
bool vis[maxn];
bool f[maxn];
vector<pair<ll,ll>> ans;
void init()
{
for(int i = 2; i <= maxn; i ++){
if(!vis[i]) prime[cnt ++] = i;
for(int j = 0; prime[j] <= maxn / i; j ++){
vis[i * prime[j]] = true;
if(i % prime[j] == 0) break;
}
}
}
void solve()
{
mem(f, 0);
ans.clear();
for(int i = n; i >= 2; i --){
if(vis[i] == true) continue;
int p = i;
int mx = (n / i) * i;
for(int j = mx; j > i; j -= i){
if(f[j]) continue;
if(p == -1) p = j;
else{
ans.pb(MP(p, j));
f[p] = 1;
f[j] = 1;
p = -1;
}
}
}
cout << ans.size() << endl;
for(int i = 0; i < ans.size(); i ++){
cout << ans[i].fi << " " << ans[i].se << endl;
}
}
int main(){
int T;
rd(T);
init();
while(T --){
rd(n);
solve();
}
return 0;
}
文章评论