题目名称 1808. [NOIP 2014]解方程
输入输出 equationa.in/out
难度等级 ★★★
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatarcqw 于2014-11-12加入
开放分组 全部用户
提交状态
分类标签
散列 NOIP/CSP 数学
分享题解
通过:186, 提交:743, 通过率:25.03%
Gravatar路人甲 100 0.146 s 4.34 MiB C++
GravatarTA 100 0.152 s 0.32 MiB C++
GravatarRivendell 100 0.235 s 8.04 MiB C++
GravatarRivendell 100 0.236 s 7.23 MiB C++
GravatarSkyo 100 0.237 s 1.26 MiB C++
GravatarRivendell 100 0.237 s 8.04 MiB C++
Gravatarchongjg 100 0.237 s 8.90 MiB C++
Gravatarchongjg 100 0.238 s 8.90 MiB C++
GravatarRivendell 100 0.253 s 8.04 MiB C++
GravatarQwQ 100 0.256 s 0.46 MiB C++
本题关联比赛
防止浮躁的小练习v0.6
防止浮躁的小练习v0.6
欢乐五一练练练
暑假综合模拟2
关于 解方程 的近10条评论(全部评论)
看懂题解之后代码量还是蛮小的...
GravatarCSU_Turkey
2017-10-24 18:11 21楼
vfk做法太吓人啦……跪烂……
P.S.:那个做法取膜次数太多会$WA$爆70,用$2147483647$验过之后再找一个大素数即可……
$UPD$:大视野老爷机害人害己……这个代码拿到那里$T$了……
GravatarHZOI_蒟蒻一只
2017-10-24 17:26 20楼
#include<map>
#include<set>
#include<list>
#include<deque>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<complex>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define LL long long
#define RG register
using namespace std;
int mod[5]={12343,19997,21121,13577,15683};
LL a[110],n,m,cnt,sum;
LL ans[1000010];
char s[110][10010];
void make(LL MOD){
for(int i=1;i<=n+1;++i){
LL x=0,len=strlen(s[i]);int f=1;
for(int j=0;j<len;++j){
if(s[i][j]=='-')f=-1;
else x=x*10+s[i][j]-48,x%=MOD;
}a[i]=(x*f)%MOD;
}
}bool yes[1000010];
int main(){
freopen("equationa.in","r",stdin);
freopen("equationa.out","w",stdout);
scanf("%lld%lld",&n,&m);
for(RG int i=1;i<=n+1;++i)scanf("%s",s[i]);memset(yes,true,sizeof(yes));
for(int i=1;i<=5;++i){
make(mod[i]);
for(RG int k=1;k<=mod[i];++k){
sum=0;
for(RG int j=n+1;j;--j)sum=sum*k+a[j],sum=(sum+mod[i])%mod[i];
if(sum)yes[k]=false;
}
for(int k=mod[i]+1;k<=m;++k)
yes[k]=yes[k-mod[i]];
}for(int i=1;i<=m;++i)if(yes[i])ans[++ans[0]]=i;
for(RG int i=0;i<=ans[0];++i)cout<<ans[i]<<'\n';
return 0;
}
Gravatarhee
2017-07-01 22:53 19楼
只过了5个点..........why......
Gravatarkilometer
2016-11-19 21:25 18楼
回复 @Asm.Def :
%%%,一开始选的素数较大,T成xiang
后来看了评论把素数√100*100000 即10000左右就A了,
GravatarGo灬Fire
2016-11-12 07:26 17楼
乘法之前不取模 这样错好几次了……
GravatarRapiz
2016-11-04 15:31 16楼
选了8个素数...压力略大......
GravatarAntiLeaf
2016-10-24 08:00 15楼
回复 @安吶。 :
我也是这样觉得的额!!!!!!!!
恶心的要死!!!!!
Gravatar森林
2016-10-06 21:13 14楼
自己都觉得自己的码风恶心..
Gravatar安呐一条小咸鱼。
2016-10-06 20:24 13楼
回复 @红莲之心炽热_血瞳洞穿无尽阴暗 :
看了评论也忘了取模的人沉默
Gravatar半汪
2016-10-06 19:23 12楼

1808. [NOIP 2014]解方程

★★★   输入文件:equationa.in   输出文件:equationa.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

已知多项式方程:$$a_0+a_1x+a_2x^2+\cdots+a_nx^n=0$$求这个方程在[1, m]内的整数解(n 和 m 均为正整数)。

【输入格式】

输入共 n+2 行。

第一行包含 2 个整数 n、m,每两个整数之间用一个空格隔开。

接下来的 n+1 行每行包含一个整数,依次为$a_1,a_2,\cdots,a_n$。

【输出格式】

第一行输出方程在[1, m]内的整数解的个数。

接下来每行一个整数,按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。

【样例输入1】

2 10
1
-2
1

【样例输出1】

1
1

【样例输入2】

2 10
2
-3
1

【样例输出2】

2
1
2

【样例输入3】

2 10
1
3
2

【样例输出3】

0

【数据规模与约定】

对于 30%的数据,$0<n\leq 2,|a_i|\leq 100,a_n\neq 0,m\leq 100$;

对于 50%的数据,$0<n\leq 100,|a_i|\leq 10^{100},a_n\neq 0,m\leq 100$;

对于 70%的数据,$0<n\leq 100,|a_i|\leq 10^{10000},a_n\neq 0,m\leq 10000$;

对于 100%的数据,$0<n\leq 100,|a_i|\leq 10^{10000},a_n\neq 0,m\leq 1000000$。

【来源】

NOIP2014 Day2 Task3