题意分析

题目给出帆船的航行路线（若干坐标点）、固定风向和船的性能参数，要求计算完成比赛的总时间。船不能直接迎风航行，如果目标方向与风向的夹角太小，就必须走折线（转向），每次转向会增加额外时间。解决方法是：对每段航程，先判断是否需要转向，如果需要就计算转向后的路径和速度（速度由航行方向与风向的夹角决定），最后累加航行时间和转向惩罚时间，输出总时间和详细航行过程。

解题思路

题目给出帆船的航行路线（若干坐标点）、固定风向和船的性能参数，要求计算完成比赛的总时间。船不能直接迎风航行，如果目标方向与风向的夹角太小，就必须走折线（转向），每次转向会增加额外时间。解决方法是：对每段航程，先判断是否需要转向，如果需要就计算转向后的路径和速度（速度由航行方向与风向的夹角决定），最后累加航行时间和转向惩罚时间，输出总时间和详细航行过程。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn = 100010;
const ll lnf = 0x3f3f3f3f3f3f3f;
int t, tot;
ll a[] = { 2,3,5,7,11,61,13,17 };
ll n, ans[maxn];
ll mul(ll x, ll y, ll z)
{
    ll sm = (ld)x / z * y;
    return ((ull)x * y - (ull)sm * z + z) % z;
}
ll ksm(ll x, ll y, ll z)
{
    ll ans = 1;
    for (ll i = y; i; i >>= 1) {
        if (i & 1) ans = mul(ans, x, z);
        x = mul(x, x, z);
    }
    return ans % z;
}
ll gcd(ll x, ll y)
{
    return y == 0 ? x : gcd(y, x % y);
}
bool rabin(ll x, ll y)
{
    if (ksm(x, y - 1, y) != 1)
        return 0;
    ll z = y - 1, sm;
    while (!(z & 1)) {
        z >>= 1;
        sm = ksm(x, z, y);
        if (sm != 1 && sm != y - 1)  return 0;
        if (sm == y - 1) return 1;
    }
    return 1;
}
bool miller(ll x)
{
    bool ans = true;
    for (int i = 0; i < 8; i++) {
        if (a[i] == x) return 1;
        ans &= rabin(a[i], x);
    }
    return ans;
}
ll Pollard(ll x)
{
    ll a, b, d, g, y, i, j;
    while (1) {
        a = b = rand() % x;
        g = rand() % x;
        y = 1; i = 0; j = 1;
        while (++i) {
            a = (mul(a, a, x) + g) % x;
            if (a > b) y = mul(y, a - b, x);
            else    y = mul(y, b - a, x);
            if (a == b || !y)    break;
            if (i < 127 || i == j) {
                d = gcd(x, y);
                if (d > 1 && d != x)   return d;
                if (i == j) {
                    b = a;
                    j <<= 1;
                }
            }
        }
    }
}
void Find(ll x)
{
    if (x <= 1)    return;
    if (miller(x)) {
        ans[tot++] = x;
        return;
    }
    ll y = Pollard(x);
    while (x % y == 0)   x /= y;
    Find(y); Find(x);
}
int main()
{
    scanf("%d", &t);
    while (t--) {
        scanf("%lld", &n);
        if (miller(n)) {
            printf("Prime\n");
            continue;
        }
        else {
            tot = 0;
            Find(n);
            ll _min = ans[0];
            for (int i = 1; i < tot; i++)
                if (ans[i] < _min) _min = ans[i];
            printf("%lld\n", _min);
        }
    }
    return 0;
}