LA 4119 Always an integer (数学)

2024-03-30 11:58
文章标签 数学 integer la always 4119

本文主要是介绍LA 4119 Always an integer (数学),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LA 4119 Always an integer


题目大意:

给定一个形如(P)/D的多项式,其中P是若干个形如Cn^E的项之和,判断他是否在所有正整数处取到整数值.
其中系数C和次数E满足如下条件:
1.E是满足0<=E<=100的整数.若E=0,则Cn^E写成C;若E=1,则Cn^E写成Cn,但当C=±1时除外(C=1时,写成n;C=-1时,写成-n).
2.C为整数.若C=±1,且E不是0或者1,则Cn^E写成n^E或者-n^E.
3.只有不在第一项的非负C前面有加号.
4.E数值严格递减.
5.C和D都在32位带符号整数范围内.

题目分析:

首先考虑如何判断该多项式是否总是整数.
可以先举例观察,设最高次数为k:
当k=0时,P为常量,求出P(1)即可.
当k=1时,P是n的一次多项式,设P=an+b,则有P(2)-P(1)=a.此时将{P(n)}看成一个数列,首项为P(1),公差为a=P(2)-P(1).所以只要求出P(1),P(2)就可以判断了.
当k=2时,P是n的二次多项式,设P=an^2+bn+c,则有P(n+1)-P(n)=2an+a+b,根据在k=1中求出的结论,也只要判断n=1和n=2能被D整除即可.也就是要求P(1),P(2),P(3)三项即可.
有数学归纳法就可以得到,对于一个最高次为k的多项式而言,只需要判断当n=1~k+1时,能否有P(n)整除D,就可以判断了.

当然此题还有一个问题——输入问题,先考虑P,因为P中每个单项式C和E都是有可能没有的,可以选择以n为分解来考虑.

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;const int maxn=100+5;
const int maxl=2000+10;
const char* output[]={"Not always an integer","Always an integer"};void getnum(char* s,int& pos,int& c,int& e)//c*n^e 一次性读取c和e两数 
{int flag=1;c=e=0;while((s[pos]<'0'||s[pos]>'9')&&s[pos]!='n') if(s[pos++]=='-') flag=-1;while(s[pos]>='0'&&s[pos]<='9') c=c*10+s[pos]-'0',++pos;if(!c) c=1; c*=flag;//若没有读到c |c|=1 int have=0;//若没有读到e 有'n',e=1 没有'n',e=0 if(s[pos]=='n') {have=1,++pos;if(s[pos]=='^') ++pos;while(s[pos]>='0'&&s[pos]<='9') e=e*10+s[pos]-'0',++pos;}if(!e) e=have; --pos;
}int C[maxn],maxe,D,kase=0;bool check(int n)
{int ans=0,p=1;//可以选择不用快速幂,递推求n的各次幂 for(int e=0;e<=maxe;e++,p=(1ll*p*n)%D)if(C[e]) ans=(0ll+ans+1ll*C[e]*p)%D;return ans==0;
}void solve()
{int always=1;//1到maxe+1依次判断 for(int i=1;i<=maxe+1;i++) if(!check(i)) {always=0;break;}printf("Case %d: %s\n",++kase,output[always]);
}char buf[maxl];bool input()
{scanf("%s",buf);if(buf[0]=='.'&&buf[1]=='\0') return false;//结束标志 memset(C,0,sizeof(C));int i,c,e;maxe=D=0;for(i=0;buf[i]!=')';i++) {//选择两个两个读入 getnum(buf,i,c,e);C[e]+=c;maxe=max(maxe,e);}i+=2;//最后读入D while(buf[i]>='0'&&buf[i]<='9') D=D*10+buf[i]-'0',++i;return true;
}int main()
{while(input()) solve();return 0;
}

这篇关于LA 4119 Always an integer (数学)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/861431

相关文章

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

uva 11044 Searching for Nessy(小学数学)

题意是给出一个n*m的格子,求出里面有多少个不重合的九宫格。 (rows / 3) * (columns / 3) K.o 代码: #include <stdio.h>int main(){int ncase;scanf("%d", &ncase);while (ncase--){int rows, columns;scanf("%d%d", &rows, &col

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2

CSP-J基础之数学基础 初等数论 一篇搞懂(一)

文章目录 前言声明初等数论是什么初等数论历史1. **古代时期**2. **中世纪时期**3. **文艺复兴与近代**4. **现代时期** 整数的整除性约数什么样的整数除什么样的整数才能得到整数?条件:举例说明:一般化: 判断两个数能否被整除 因数与倍数质数与复合数使用开根号法判定质数哥德巴赫猜想最大公因数与辗转相除法计算最大公因数的常用方法:举几个例子:例子 1: 计算 12 和 18

2024年AMC10美国数学竞赛倒计时两个月:吃透1250道真题和知识点(持续)

根据通知,2024年AMC10美国数学竞赛的报名还有两周,正式比赛还有两个月就要开始了。计划参赛的孩子们要记好时间,认真备考,最后冲刺再提高成绩。 那么如何备考2024年AMC10美国数学竞赛呢?做真题,吃透真题和背后的知识点是备考AMC8、AMC10有效的方法之一。通过做真题,可以帮助孩子找到真实竞赛的感觉,而且更加贴近比赛的内容,可以通过真题查漏补缺,更有针对性的补齐知识的短板。

一些数学经验总结——关于将原一元二次函数增加一些限制条件后最优结果的对比(主要针对公平关切相关的建模)

1.没有分段的情况 原函数为一元二次凹函数(开口向下),如下: 因为要使得其存在正解,必须满足,那么。 上述函数的最优结果为:,。 对应的mathematica代码如下: Clear["Global`*"]f0[x_, a_, b_, c_, d_] := (a*x - b)*(d - c*x);(*(b c+a d)/(2 a c)*)Maximize[{f0[x, a, b,

2024年高教社杯数学建模国赛最后一步——结果检验-事关最终奖项

2024年国赛已经来到了最后一天,有必要去给大家讲解一下,我们不需要过多的去关注模型的结果,因为模型的结果的分值设定项最多不到20分。但是如果大家真的非常关注的话,那有必要给大家讲解一下论文结果相关的问题。很多的论文,上至国赛优秀论文下至不获奖的论文并不是所有的论文都可以进行完整的复现求解,大部分数模论文都为存在一个灰色地带。         白色地带即认为所有的代码均可运行、公开

CSP-J基础之数学基础 初等数论 一篇搞懂(二)

文章目录 前言算术基本定理简介什么是质数?举个简单例子:重要的结论:算术基本定理公式解释:举例: 算术基本定理的求法如何找出质因数:举个简单的例子: 重要的步骤:C++实现 同余举个例子:同余的性质简介1. 同余的自反性2. 同余的对称性3. 同余的传递性4. 同余的加法性质5. 同余的乘法性质 推论 总结 前言 在计算机科学和数学中,初等数论是一个重要的基础领域,涉及到整数