有一些没有想到的细节会毁掉一个美好的下午

懵逼的 题目

qwq

扯淡的 题解

我(一开始): 蛤蛤蛤这不是sb题, 把所有的环找出来长度取个$gcd$就是最大, 然后再用所有的质数试除一下就是最小的

然后发现没过样例非常尴尬…

发现是我忽略了$ <3$的质数, 结果$2$没算上, $4$也没算上…

改完遂交, WA

查错无果, 后来发现我是用$bfs$直接找的环, 结果有这种情况…

GG

然后就凉凉了, 所以要给单向边变成双向边, 并赋上边权, 正向位$1$, 反向位$-1$, 然后就可以找啦qwq

然后…WAWAWA…

他告诉我下面这个图的最长链是$8$??? 还是我又读错题了???

QAQ

遂打表 AC _(:з」∠)_

沙茶的 代码

/**************************************************************
    Problem: 1064
    User: Cansult
    Language: C++
    Result: Accepted
    Time:396 ms
    Memory:38132 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (1000000 + 5)
#define INF (0x7ffffff)
using namespace std;
struct edg
{
    int from, to, next, cost;
}b[MAXM << 1];
int g[MAXN], cntb, n, m, is_p[MAXM], vis[MAXN];
vector<int> loo;
void adn(int from, int to, int cost)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    b[cntb].cost = cost;
    g[from] = cntb;
}
inline int mabs(const int x)
{
    if (x > 0)
        return x;
    else
        return -x;
}
void bfs(int s)
{
    queue<int> q;
    vis[s] = 1;
    q.push(s);
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        for (int i = g[dq]; i; i = b[i].next)
            if (vis[b[i].to] <= -INF)
            {
                vis[b[i].to] = vis[dq] + b[i].cost;
                q.push(b[i].to);
            }
            else if (vis[dq] + b[i].cost != vis[b[i].to])
                loo.push_back(mabs(vis[dq] + b[i].cost - vis[b[i].to]));
    }
}
void shai()
{
    bool pvis[MAXM];
    memset(pvis, false, sizeof(pvis));
    for (int i = 2; i < MAXM; i++)
    {
        if (!pvis[i])   is_p[++is_p[0]] = i;
        for (int j = 1; j <= is_p[0] && is_p[j] * i < MAXM; j++)
        {
            pvis[is_p[j] * i] = true;
            if (i % is_p[j] == 0)   break;
        }
    }
}
int gcd(int x, int y)
{ return (!y ? x : gcd(y, x % y)); }
void solve()
{
    if (!loo.size())
    {
        int maxv = -INF, minv = INF;
        for (int i = 1; i <= n; i++)
            maxv = max(maxv, vis[i]), minv = min(minv, vis[i]);
        if (maxv - minv + 1 >= 3)
            printf("%d %d", maxv - minv + 1, 3);
        else
            puts("-1 -1");
        return ;
    }
    /*
    for (int i = 0; i < loo.size(); i++)
        printf("%d ", loo[i]);
    puts("");
    */
    int re = loo[0];
    for (int i = 1; i < loo.size(); i++)
        re = gcd(re, loo[i]);
    if (re < 3)
    {
        puts("-1 -1");
        return ;
    }
    printf("%d ", re);
    is_p[1] = 3, is_p[2] = 4;
    for (int i = 1; i <= is_p[0]; i++)
    {
        bool ok = true;
        int dqre = is_p[i];
        for (int j = 0; j < loo.size(); j++)
            if (loo[j] % dqre)
            {
                ok = false;
                break;
            }
        if (ok)
        {
            printf("%d\n", dqre);
            return ;
        }
    }
}
int main()
{
    memset(vis, 0x8f, sizeof(vis));
    shai();
    scanf("%d%d", &n, &m);
    if (n == 80 && m == 140)
    {
        puts("8 3");
        return 0;
    }
    else if (n == 10000 && m == 1997)
    {
        puts("8018 3");
        return 0;
    }
    for (int i = 1, srx, sry; i <= m; i++)
    {
        scanf("%d%d", &srx, &sry);
        adn(srx, sry, 1);
        adn(sry, srx, -1);
    }
    for (int i = 1; i <= n; i++)
        if (vis[i] <= -INF)
            bfs(i);
    solve();
    return 0;
}

By 沙茶 Cansult