NOIP 2014 Senior 6 - 解方程

题目

思路 1
肯定一开始就能想到高精度吧。不过这个数据规模看上去有点非常大,而且需要写的有比较、负数、加法、乘法、乘方、高精度输入。。。反正比赛时我是不愿意相信会单独考这么一个高精度的。
听说能拿50分。

思路 2
加法和乘法以及乘方?嗯,以前遇到过的,这样的操作是符合模运算规则的。所以我们可以使用模运算,枚举除数,进行多次判断,如果都满足算出来等于0,那我们就可以说这个x代进去算出来应该是0,如果有任何一个都不满足,那我们说这个x代进去算肯定不是0。
所以选哪些作为除数呢?又要选多少呢?毫无疑问,这个除数必须是个质数。在一开始,我选择了10个较大质数,结果过了7个点:最后3个点因为m太大超时了。

这个思路还是有一些东西值得学(复)习的,比如:
(1)输入大整数
根据读入优化的思路写一波

bool readIn(char* str, int* l) //重载,返回是否为负数。我们保证str为空串。
{
    bool minus = false;
    int& length = *l;
    length = 0;
    int ch = getchar();
    while (!(ch == '-' || ch >= '0' && ch <= '9')) ch = getchar();
    if (ch == '-')
    {
        minus = true;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        str[length++] = ch - '0'; //就不保存字符了
        ch = getchar();
    }
    return minus;
}

(2)大整数求余
一个函数就解决,不要想到去写高精度除法= =。

INT Mod(int index, INT mod)
{
    INT ret = 0;
    for (int i = 0; i < length[index]; i++)
    {
        ret *= digit;
        ret += origin[index][i]; //刚刚输入的字符串
        ret %= mod;
    }
    if (minus[index])
    {
        ret = -ret;
        ret += mod; //模运算法则
    }
    return ret % mod;
}

(3)秦九韶算法
终于把它从数学书上搬过来了。。。

//for (int i = 0; i < size; i++) //预处理系数,将系数分别与那几个质数求余
//{ //size为质数个数
//  for(int j = 0; j <= n; j++)
//  {
//      A[i][j] = Mod(j, Prime[i]);
//  }
//}

INT Polynomial(INT x, int modIndex)
{
    INT ret = A[modIndex][n];
    for (int i = n; i >= 1; i--)
    {
        ret *= x;
        ret %= Prime[modIndex];
        ret += A[modIndex][i - 1];
        ret %= Prime[modIndex];
    }
    return ret;
}

记不到?模拟几遍就写出来了,不多说。

主程序

    std::vector<int> ans;
    for (int x = 1; x <= m; x++)
    {
        bool bOk = true;
        for (int i = 0; i < size; i++)
        {
            if (Polynomial(x, i) != 0)
            {
                bOk = false;
                break;
            }
        }
        if (bOk)
        {
            ans.push_back(x);
        }
    }
    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); i++)
    {
        printf("%d\n", ans[i]);
    }

可以发现,即使在判断时有个break,它也不会起太大的作用,因为它最多只能加速一个数,这也是这个算法只能得70分的原因。

思路 3
如果我们确定了一个数可能是解,是否可以推算出其它数也可能是解呢?答案是肯定的。把多项式的和用秦九韶算法的形式写出来,发现当x加p后余上p的值不变,即若f(x)0(modp),那么f(x+p)0(modp)。这时,我们可以仅枚举[1, p],把所有符合条件的x的x + kp都标记成可能是解,然后用类似于筛法的思想,检查之前所有可能是解的值。
所以使用筛法时,应使用一个较小的(但不能太小)的质数,最后检查时,应使用较大的质数。具体要用多少个来检查呢?建议考试时多用几个来检查,保险一点。实测只需要用一个来筛,一个来检查就够了。

参考代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
using std::cin;
using std::cout;
using std::endl;
typedef long long INT;
int readIn()
{
    bool minus = false;
    int a = 0;
    int ch = getchar();
    while (!(ch == '-' || ch >= '0' && ch <= '9')) ch = getchar();
    if (ch == '-')
    {
        minus = true;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        a *= 10;
        a += ch;
        a -= '0';
        ch = getchar();
    }
    if(minus) a = -a;
    return a;
}
bool readIn(char* str, int* l)
{
    bool minus = false;
    int& length = *l;
    length = 0;
    int ch = getchar();
    while (!(ch == '-' || ch >= '0' && ch <= '9')) ch = getchar();
    if (ch == '-')
    {
        minus = true;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        str[length++] = ch - '0';
        ch = getchar();
    }
    return minus;
}

const int maxn = 105;
int n, m;
bool minus[maxn];
int length[maxn];
const INT digit = 10;
char origin[maxn][10005];
const INT Prime[] =
{
    10007, //用于快速求值
    199999769 //用于准确判断
};
const int size = sizeof(Prime) / sizeof(INT);
INT A[size][maxn];

INT Mod(int index, INT mod)
{
    INT ret = 0;
    for (int i = 0; i < length[index]; i++)
    {
        ret *= digit;
        ret += origin[index][i];
        ret %= mod;
    }
    if (minus[index])
    {
        ret = -ret;
        ret += mod;
    }
    return ret % mod;
}

INT Polynomial(INT x, int modIndex)
{
    INT ret = A[modIndex][n];
    for (int i = n; i >= 1; i--)
    {
        ret *= x;
        ret %= Prime[modIndex];
        ret += A[modIndex][i - 1];
        ret %= Prime[modIndex];
    }
    return ret;
}

void run()
{
    n = readIn();
    m = readIn();
    for (int i = 0; i <= n; i++)
    {
        minus[i] = readIn(origin[i], &length[i]);
    }
    for (int i = 0; i < size; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            A[i][j] = Mod(j, Prime[i]);
        }
    }

    std::vector<bool> isAns(m + 1);
    std::vector<int> ans;
    for (int x = 1; x < Prime[0]; x++)
    {
        if (!Polynomial(x, 0))
        {
            for(int i = x; i <= m; i += Prime[0])
            {
                isAns[i] = true;
            }
        }
    }
    for (int x = 1; x <= m; x++)
    {
        if(isAns[x] && !Polynomial(x, 1))
        {
            ans.push_back(x);
        }
    }
    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); i++)
    {
        printf("%d\n", ans[i]);
    }
}

int main()
{
    run();
    return 0;
}

怎么得到素数呢?可以自己另写程序使用埃式筛法求得。所以,这道题还是算是有点数论的味道(勿喷)。

bool isntPrime[200000000];
int from = readIn();
int n = readIn();

int to = sqrt(n);
for(int i = 2; i <= to; i++)
{
    if(!isntPrime[i])
    {
        for(int j = i * i; j <= n; j += i)
        {
            isntPrime[j] = true;
        }
    }
}
版权声明:本文为lycheng1215原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lycheng1215/article/details/75172872

智能推荐

Linux搭建LAMP,源码安装

Linux搭建LAMP,源码安装 LAMP是Linux Apache MySQL PHP的简写,即把Apache、MySQL以及PHP安装在Linux系统上,组成一个环境来运行PHP的脚本语言,通常是网站。Apache 是最常用的Web服务软件,而MySQL是比较小型的数据库软件,这两个软件以及PHP都可以安装到Windows的机器上。 我们可以把Apache+PHP安装在一台机器上,再把MySQ...

模拟按键 —— 鼠标

背景 之前写自动化脚本的时候总是遇到一些很尴尬的问题: 跑脚本时模拟鼠标按键时,光标是真实的跑到了那个位置的,也就是说跑脚本的时候会很影响电脑的正常使用,导致不得不开一个虚拟机专门跑。 另外因为光标只有一个所以很难实现多线程去同时操作多个窗口,当线程1 模拟鼠标但还没有结束时,线程2 已经开始执行模拟操作,这就导致了线程1 的模拟操作被终止了,被迫之下只能开多个虚拟机(但实在太占用性能🙄) 解决...

Hibernate学习总结(一)

一、Hibernate简介 一个持久层的ORM框架。ORM:Object Relational Mapping(对象关系映射)。指的是将一个Java中的对象与关系型数据库中的表建立一种映射关系,从而操作对象就可以操作数据库中的表。 二、Hibernate入门 1、创建一个项目,引入jar包 hibernate用到的jar包 2、创建表 3、创建实体类 4、创建映射(*****) 映射需要通过XML...

Linux系统NFS

文章目录 1. nfs简介 1.1 nfs特点 1.2 使用nfs的好处 1.3 nfs的体系组成 1.4 nfs的应用场景 2. nfs工作机制 2.1 RPC 2.2 NIS 2.3 nfs工作机制 3. exports文件的格式 4. nfs管理 5. 作业 5.1手动搭建一个nfs服务器 5.1.1开放/nfs/shared目录,供所有用户查阅资料 5.1.2 开放/nfs/upload目...

关于java中String,StringBuffer,StringBuilder的区别以及StringBuffer,StringBuilder的安全性问题

这里的结果就是正确的然后我们来看他的append方法 它在前边加了一个synchronized来修饰,相当于同时只能有一个线程来访问他,这样就不会产生上边的问题但同时他的效率也就比StringBuilder低,...

猜你喜欢

Django连接现有mysql数据库

1、打开cmd后cd到项目位置 2、建立项目 django-admin startproject test2 3、编辑项目中的配置文件, mysite/settings.py ,告诉Django你的数据库连接参数和数据库名。具体的说,要提供 DATABASE_NAME , DATABASE_ENGINE , DATAB...

ShareSDK新浪微博登录时报错error:redirect_uri_mismatch

今天用 ShareSDK 做第三方登录的时候碰到个问题,明明在微博平台的应用审核已经通过了,但是调用登录接口的时候一直报错,错误如下: 出现这个错误是因为在微博开放平台上没有设置回调地址,或者设置的回调地址与本地XML中的地址不一致。 在sharesdk.xml文件当中对于微博的设置: 其中RedirectUrl为设置的回调地址,这里的地址必须要与微博开发平台设置的地址相同,否则就会出现上面的错误...

python解析网络封包方法

2019独角兽企业重金招聘Python工程师标准>>> 在使用Python解析网络数据包时,使用网络字节序解析,参见下表。 C语言的数据类型和Python的数据类型对照表请参见下表。 接下来对封包与解包进行举例说明。 version type id content unsigned short unsigned short unsigned int unsigned int 封包...

python3:时间方法,异常处理,系统文件相关模块(os)

文章目录 时间方法 time模块 时间表示方法: time模块的方法 datetime模块 异常处理 触发异常 创建mydiv.py脚本,要求如下: 创建myerror.py脚本,要求如下: os模块 实现ls -R(os.walk) os.path pickle模块 记账脚本 时间方法 time模块 时间表示方法: 时间戳:自1970-1-1 0:00:00到某一时间点之间的秒数 UTC时间:世...

负载均衡群集——LVS+DR模型

一、实验组成 调度器 192.168.100:41 web1 192.168.100:42 web2 192.168.100.43 NFS共享服务器 192.168.100.44 二、实验拓扑 三、实验配置 3.1在调度器配置:192.168.100.41 配置虚拟IP地址(VIP) 调整/proc响应参数 对于 DR 群集模式来说,由于 LVS 负载调度器和各节点需要共用 VIP 地址,应该关闭...