2020 CCPC 威海 - A. Golden Spirit(思维)，D. ABC Conjecture(大数分解 / 思维)

A. Golden Spirit

题意
一道河上有座桥，两岸分别有 $n$ 个人。
现这 $2n$ 个人都要到对岸去，游玩至少 $x$ 分钟后回到原来的河岸。
要帮助这 $2n$ 个人渡河。
每次渡河最多带一个人，时间为 $t$。
问，满足所有人的要求最少花多少时间？

思路
在最理想的情况下，帮助者没有一点时间浪费，当他把所有人都运到其对应对岸后，立即可以将该河岸首次运过来的人运回去。
但是可能甚至首次运过来的人都没有到所需的游玩时间，所以帮助者可能需要等待。

假设有河岸 A 和 B，起初帮助者在河岸 A，那么将所有人分别运到其对应河岸后，帮助者位于河岸 A。

这时就面临一个问题，帮助者是继续在该河岸 A 等待首次运到河岸 A 的人，还是自己到对岸 B 去等首次运到河岸 B 的人？
前者所需时间为：运输所有人的时间 4nt + 等待时间（最少游玩时间 x - 首人已经游玩时间 2nt-2t）
后者所需时间为：运输所有人的时间 4nt + 自己到对岸的时间 t + 等待时间（最少游玩时间 x - 首人已经游玩时间 2nt + t - t）
因为不确定两者的大小，所以需要将两者取 min。

Code:

#include<bits/stdc++.h>
using namespace std;

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];

signed main(){
    
	cin >> T;
	while(T--)
	{
    
		int x, t;
		cin >> n >> x >> t;
		
		int ans1 = 4*n*t + t + max(0ll, x - (2*n*t + t - t));
		int ans2 = 4*n*t + max(0ll, x - (2*n*t - 2*t));
		cout << min(ans1, ans2) << endl;
	}
	
	return 0;
}

经验

• 当不确定所有情况哪种最优时，需要将所有情况的答案取最小值；
• 有些情况下不要写太多的 if else，而是尽量将其抽象到一种大情况中。

---

D. ABC Conjecture

题意
给定一个数 c，判断是否存在 a, b 满足下面条件：

• a + b = c
• abc 的所有质因子的乘积 不超过 c

$1\le c\le 10^{18}$

思路
打表发现：能够满足的 c 分解的所有质因子都只出现一次。
所以对于给定的 c，只需判断其是否存在出现不止一次的质因子即可。

但是 c 很大，而常用的分解质因数代码的时间复杂度为O(logn)，会超时。
所以需要用特殊的方法来做。

方法1：

• 按照分解质因数的思路将 c 的所有不超过 1e6 的质因数分解，判断其个数是否出现两次及以上。
• 如果 1e6 内的质因数筛完之后发现 c 不为1，那么说明 c 还存在最多两个大于 1e6 的质因数（假设存在3个，那么相乘后大于1e18，矛盾）。
  我们不是要求出这两个质因子，而只是想判断这两个质因子是否相同。所以将最后的 c 取根号取整，判断其是否为平方数。如果是平方数，那么最后的两个质因子就是相同的。

Code1:

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'

const int N = 1000010, mod = 1e9+7;
int T, n, m;
int a[N];
int f[N];
int prim[N];
int cnt;
int maxa = 1e6;

signed main(){
    
	Ios;
	cin >> T;
	while(T--)
	{
    
		cin >> n;
		
		int flag = 0;
		for(int i=2; i<=maxa; i++)
		{
    
			if(n % i == 0)
			{
    
				int cnt = 0;
				while(n % i == 0) n /= i, cnt++;
				if(cnt != 1) flag = 1;
			}
		}
		
		if(n != 1){
    
			int sq = sqrt(n);
			if(sq * sq == n) flag = 1;
		}
		
		if(flag) cout << "yes\n";
		else cout << "no\n";
	}
	
	return 0;
}

方法2
直接上大数质因子分解模板，判断是否有质因子出现两次及以上。
Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pr;
ll pmod(ll a, ll b, ll p) {
     return (a * b - (ll)((long double)a / p * b) * p + p) % p; }
ll gmod(ll a, ll b, ll p)
{
    
    ll res = 1;
    while (b)
    {
    
        if (b & 1)
            res = pmod(res, a, p);
        a = pmod(a, a, p);
        b >>= 1;
    }
    return res;
}
inline ll gcd(ll a, ll b)
{
     
    if (!a)
        return b;
    if (!b)
        return a;
    int t = __builtin_ctzll(a | b);
    a >>= __builtin_ctzll(a);
    do
    {
    
        b >>= __builtin_ctzll(b);
        if (a > b)
        {
    
            ll t = b;
            b = a, a = t;
        }
        b -= a;
    } while (b);
    return a << t;
}
bool Miller_Rabin(ll n)
{
    
    if (n == 46856248255981ll || n < 2)
        return false; 
    if (n == 2 || n == 3 || n == 7 || n == 61 || n == 24251)
        return true;
    if (!(n & 1) || !(n % 3) || !(n % 61) || !(n % 24251))
        return false;
    ll m = n - 1, k = 0;
    while (!(m & 1))
        k++, m >>= 1;
    for (int i = 1; i <= 20; ++i)
    {
    
        ll a = rand() % (n - 1) + 1, x = gmod(a, m, n), y;
        for (int j = 1; j <= k; ++j)
        {
    
            y = pmod(x, x, n);
            if (y == 1 && x != 1 && x != n - 1)
                return 0;
            x = y;
        }
        if (y != 1)
            return 0;
    }
    return 1;
}
ll Pollard_Rho(ll x)
{
    
    ll n = 0, m = 0, t = 1, q = 1, c = rand() % (x - 1) + 1;
    for (ll k = 2;; k <<= 1, m = n, q = 1)
    {
    
        for (ll i = 1; i <= k; ++i)
        {
    
            n = (pmod(n, n, x) + c) % x;
            q = pmod(q, abs(m - n), x);
        }
        t = gcd(x, q);
        if (t > 1)
            return t;
    }
}
map<long long, int> m;
void fid(ll n)
{
    
    if (n == 1)
        return;
    if (Miller_Rabin(n))
    {
    
        pr = max(pr, n);
        m[n]++;
        return;
    }
    ll p = n;
    while (p >= n)
        p = Pollard_Rho(p);
    fid(p);
    fid(n / p);
}
int main()
{
    
    int T;
    ll n;
    scanf("%d", &T);
    while (T--)
    {
    
        m.clear();
        scanf("%lld", &n);
        pr = 0;
        fid(n);
		int flag = 0;
        for (map<long long, int>::iterator c = m.begin(); c != m.end(); c++)
	        if(c->second != 1) flag = 1;

		if(flag) printf("yes\n");
		else printf("no\n");
    }
    return 0;
}

打表代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define endl '\n'

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];

vector<int> v, v1, v2;
set<int> st, s;

void div(int x, vector<int> &v)
{
    
	v.clear();
	for(int i=2;i<=x/i;i++)
	{
    
		if(x%i == 0)
		{
    
			while(x%i == 0) x /= i;
			v.push_back(i);
		}
	}
	if(x != 1) v.push_back(x);
}

signed main(){
    
	for(int i=1;i<=1000;i++)
	{
    
		st.clear();
		div(i, v);
		for(int x : v) st.insert(x);
		
		int flag = 0;
		for(int j=1;j<i;j++)
		{
    
			s = st;
			
			int x = j, y = i - x;
			div(x, v1);
			div(y, v2);
			
			for(int x : v1) s.insert(x);
			for(int x : v2) s.insert(x);
			
			int sum = 1;
			for(int x : s){
    
				sum *= x;
			}
			if(sum < i){
    
				flag = 1;
				break;
			}
		}
		if(!flag){
    
			cout << i << ":";
			for(int x : st) cout << x << " ";
			cout << endl;
		}
	}
	
	return 0;
}

经验

• 没有思路的时候先打个表；
• 判断一个数是不是平方数，sqrt(n)要取整之后再相乘；
• 大数质因子分解模板。

---