我的个人记载
  • About Me
不知名小站
Never Give Up
  1. 首页
  2. 多校训练
  3. 正文

2020多校训练-第四场

2020年08月14日 80点热度 0人点赞 0条评论

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;
}

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2020年08月14日

框框

喜欢算法,喜欢编程。

打赏 点赞
< 上一篇
下一篇 >

文章评论

取消回复

框框

喜欢算法,喜欢编程。

文章归档
  • 2020年10月
  • 2020年8月
  • 2020年7月
  • 2020年1月
  • 2019年11月
  • 2019年8月
  • 2019年7月
分类目录
  • 2008年哈尔滨区域赛
  • 2018焦作网络赛
  • Greater New York Region 2014
  • kuangbin并查集专题
  • Kuangbin数论专题
  • NZPC 2017
  • upc个人训练赛
  • 位运算
  • 博弈论
  • 多校训练
  • 搜索
  • 数据结构
  • 数论
  • 杭电多校训练第五场
  • 深入理解计算机基础/CSAPP
  • 算法模板
  • 线段树

COPYRIGHT © 2020 我的个人记载. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

苏ICP备19034952号-1