[HEOI2012]AKAI的数学作业

C++(g++ 7.5.0) 解法, 执行用时: 9ms, 内存消耗: 488K, 提交时间: 2022-11-04 23:39:38

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

const int N = 1e8, mod = 1e9 + 7;

typedef long long LL;
typedef pair<int, int> PII;

int n;
int a0, an;
vector<int> a[2], v;
vector<double> b;
vector<PII> ans;

LL ksm(LL a, LL b)
{
    LL res = 1;
    while(b)
    {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int gcd(int a, int b)
{
    return !b ? a : gcd(b, a % b);
}

bool check(int p, int q)
{
    LL x = p * ksm(q, mod - 2) % mod;
    LL res = 0, nt = 1;

    for(int i = 0; i <= n; i ++)
    {
        res = res + nt * v[i] % mod, res %= mod;
        nt = nt * x % mod;
    }
    return (res + mod) % mod == 0;
}

bool cmp(PII a, PII b)
{
    return 1LL * a.first * b.second < 1LL * a.second * b.first;
}

void init(int x, int id)
{
    if(x < 0) x = -x;
    for(int i = 1; i * i <= x; i ++)
    {
        if(x % i) continue;
        a[id].push_back(i);
        if(i * i != x) a[id].push_back(x / i);
    }
}

int main(void)
{
    IOS;
    cin >> n;
    a0 = -N;
    for(int i = 0; i <= n; i ++)
    {
        int x;
        cin >> x;
        if(a0 == -N && x) a0 = x;
        an = x;
        v.push_back(x);
    }

    init(a0, 0), init(an, 1); 
    for(int i = 0; i < a[0].size(); i ++)
    {
        for(int j = 0; j < a[1].size(); j ++)
        {
            int p = a[0][i], q = a[1][j];
            if(gcd(p, q) == 1)
            {
                if(check(-p, q))
                    ans.push_back({-p, q});
                if(check(p, q))
                    ans.push_back({p, q});
            }
        }
    }
    
    if(check(0, 1)) ans.push_back({0, 1});
    sort(ans.begin(), ans.end(), cmp);
    
    cout << ans.size() << endl;
    for(int i = 0; i < int(ans.size()); i ++)
    {
        int p = ans[i].first, q = ans[i].second;
        if(q == 1)
            cout << p << endl;
        else 
            cout << p << "/" << q << endl;
    }
    return 0;
}

/*
a0 + a1x + a2x^2 + ... + anx^n = 0;
考虑 有理数 x = p / q， gcd(x, y) = 1;

a0 * q^n ≡ 0 (mod p)
an * p^n ≡ 0 (mod q)

枚举 a0 和 an 的约数
*/

C++14(g++5.4) 解法, 执行用时: 11ms, 内存消耗: 3064K, 提交时间: 2019-08-12 15:22:37

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Mod = 1e9+7;
const double eps = 1e-7;

vector<int> div(int x){
    x = abs(x);
    vector<int> a;
    for(int i=1;i*i<=x;i++)
    {
        if( x%i == 0 )
        {
            a.push_back(i);
            if( i*i != x )
                a.push_back(x/i);
        }
    }
    return a;
}

ll mypow(ll a,ll b){
    ll inv = 1;
    while( b )
    {
        if( b&1 )  inv = inv*a%Mod;
        a = a*a%Mod;
        b >>= 1;
    }
    return inv;
}

int n;
int a[233];

vector<int> P,Q;

struct Hex{
    ll p,q;
    double x;
    Hex(ll p=0,ll q=0,double x=0):p(p),q(q),x(x){}
};

int tol,sum;
Hex ans[111110];

int dcmp(double x){
    if( fabs(x) <= eps )  return 0;
    return x > 0 ? 1 : -1;
}

bool cmp(Hex a,Hex b){
    return a.x < b.x;
}

int gcd(int a,int b){
    return b == 0 ? a : gcd(b,a%b);
}

bool calc(ll p,ll q){
    // cout<<p<<" "<<q<<endl;
    int x = p*mypow(q,Mod-2)%Mod;
    ll res = 0;
    ll pro = 1;
    for(int i=0;i<=n;i++)
    {
        res = (res + pro*a[i]%Mod)%Mod;
        pro = pro*x%Mod;
    }
    return (res + Mod)%Mod == 0;
}

void Out(Hex h){
    if( h.q == 1 )  printf("%lld\n",h.p);
    else printf("%lld/%lld\n",h.p,h.q);
    return ;
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<=n;i++)
        scanf("%d",&a[i]);
    int l = 0;
    while( a[l] == 0 )  l++;
    P = div(a[l]);
    Q = div(a[n]);
    for(int i=0;i<P.size();i++)
        for(int j=0;j<Q.size();j++)
        {
            int p = P[i],q = Q[j];
            if( gcd(p,q) != 1 )  continue;
            if( calc(p,q) )  ans[tol++] = Hex(p,q,1.0*p/q);
            if( calc(-p,q) )  ans[tol++] = Hex(-p,q,-1.0*p/q);
        }
    if( calc(0,1) )  ans[tol++] = Hex(0,1,0);
    // cout<<tol<<endl;
    // cout<<ans[1].p<<" "<<ans[1].q<<endl;1
    if(tol == 0){puts("0");return 0;}
    sort(ans,ans+tol,cmp);
    sum = 1;
    for(int i=1;i<tol;i++)
        if( dcmp(ans[i].x-ans[i-1].x) != 0 )  sum++;
    printf("%d\n",sum);
    Out(ans[0]);
    for(int i=1;i<tol;i++)
        if( dcmp(ans[i].x - ans[i-1].x) != 0 )  Out(ans[i]);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 7ms, 内存消耗: 416K, 提交时间: 2020-08-22 20:43:56

#include<cstdio>
#include<algorithm>
#include<cmath>
#define eps 1e-12
using namespace std;
typedef long double ld;
const int N = 105;
int a[N + 1];pair<int, int>p[N + 1];
int cmp(pair<int, int>x, pair<int, int>y){return 1ll * x.first * y.second < 1ll * y.first * x.second;}
int gcd(int x, int y){
	int r;
	while(y)r = x % y, x = y, y = r;
	return x;
}
int f(ld x, int n){
	int i;ld y;
	for(i = n, y = 0;i >= 0;i--)y = y * x + a[i];
	return abs(y) < eps;
}
int main(){
	int n, i, j, m, k, x, y;
	scanf("%d", &n);
	for(i = 0;i <= n;i++)scanf("%d", &a[i]);
	if(!n){
		if(a[0])printf("0");
		else printf("1\n0/1");
		return 0;
	}x = abs(a[m = 0]);
	if(!x){
		p[m = 1] = make_pair(0, 1);
		for(i = 1;i <= n && !a[i];i++);
		x = abs(a[i]);
		for(j = i;j <= n;j++)a[j - i] = a[j];
		n -= i;
	}y = abs(a[n]);
	if(!n){
		printf("1\n0/1");
		return 0;
	}
	for(i = 1;i <= x / i;i++)if(!(x % i))
		for(j = 1;j <= y / j;j++)if(!(y % j)){
			if(f((ld)i / j, n)){
				k = gcd(i, j);
				p[++m] = make_pair(i / k, j / k);
			}if(f(-(ld)i / j, n)){
				k = gcd(i, j);
				p[++m] = make_pair(-i / k, j / k);
			}
			if(f((ld)x / i / j, n)){
				k = gcd(x / i, j);
				p[++m] = make_pair(x / i / k, j / k);
			}if(f(-(ld)x / i / j, n)){
				k = gcd(x / i, j);
				p[++m] = make_pair(-x / i / k, j / k);
			}
			if(f((ld)i / (y / j), n)){
				k = gcd(i, y / j);
				p[++m] = make_pair(i / k, y / j / k);
			}if(f(-(ld)i / (y / j), n)){
				k = gcd(i, y / j);
				p[++m] = make_pair(-i / k, y / j / k);
			}if(f((ld)x / i / (y / j), n)){
				k = gcd(x / i, y / j);
				p[++m] = make_pair(x / i / k, y / j / k);
			}if(f(-(ld)x / i / (y / j), n)){
				k = gcd(x / i, y / j);
				p[++m] = make_pair(-x / i / k, y / j / k);
			}
		}sort(p + 1, p + m + 1, cmp);
	m = unique(p + 1, p + m + 1) - p - 1;
	printf("%d\n", m);
	for(i = 1;i <= m;i++)
		if(p[i].second == 1)printf("%d\n", p[i].first);
		else printf("%d/%d\n", p[i].first, p[i].second);
	return 0;
}

详情