首页 > 代码库 > A1063. 求导函数的值
A1063. 求导函数的值
题目：http://www.tsinsen.com/A1063
这道题有两个点：
第一个，不要做重复的计算，我看有些提交是梅ai*x0^n就放到求次方的方程里面代一遍，加大了时间复杂度，本来时间复杂度是o（n)的。
只需要在for循环中完成次方的递增就好，同时累加。
第二个是a*b mod c=(a mod c)*(b mod c)
证明很简单，将a,b分成可以被c整除的部分au,bu.不能整除的部分ah,bh.
a*b=(au+ah)*(bu+bh)=au*bu+au*bh+ah*bu+ah*bh
上式只有最后一项会产生余数。并且ah=a mod c;bh=b mod c;
代码：
#include <iostream>
#include <stdio.h>
using namespace std;
int a[101];
int b[101];
int n,x0;
long long int result,step;
int main()
{
cin>>n>>x0;
getchar();
for(int i=0;i<=n;i++)
cin>>a[i];
for(int i=0; i<=n-1; i++)
{
b[i]=a[i+1]*(i+1);
}
step=x0;
result=b[0];
for(int i=1; i<n; i++)
{
result=(result%9999+step*b[i]%9999)%9999;
step=step*x0%9999;
}
cout << (result+9999)%9999 << endl;
return 0;
}
至于本题目中要求-1%9999=9998;所以要先将负数变成正数。
A1063. 求导函数的值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。