计算错误（root（1，x）* A [1] + root（2，x）* A [2] + ... + root（N，x）* A [N]）％1000000007其中root（i ，x）是x的第i个根。 [英] mistake in calculating (root(1, x)*A[1] + root(2, x)*A[2] + ... + root(N, x)*A[N])%1000000007 where root(i, x) is ith root of x.

问题描述

#include<cstdio>
#include<iostream>
#include<cmath>
#include <float.h>

#define sBig long long int

using namespace std;
sBig CONS = 1000000007;

inline sBig mod(sBig a)
{ return (a%CONS+CONS)%CONS; }


sBig a[10010], rem[10010];
int n;
sBig solve(sBig x)
{
    sBig res;
    res = mod(mod(x)*a[1]);
    int j = 2;
    for(;  j <= n ; j++)
    {

        int nrt = floor(pow(x,1.0/(double)j));
        if(nrt < 2)
            break;
        res = mod(res +  mod((nrt)*a[j]));
    }
    if(n > 1)
        res = mod(res + rem[j]);

    return res;
}
main()
{
    int  q;
    sBig x;
        scanf("%d%d",&n,&q);

        rem[n+1] = 0;
        for(int i = 1; i <= n; i++)
          {
                scanf("%lld",&a[i]);
          }


        for(int i = n; i > 0; i--)
            rem[i] = mod(rem[i+1] + a[i]);

        for(int i = 0; i < q  ; i++)
        {
            scanf("%lld",&x);
            printf("%lld ",solve(x));
        }
return 0;
}

i我希望得到x，n和a [i]的每一个值的正确答案，其中

-10 ^ 9< = a [i]< = 10 ^ 9

1< = x< = 10 ^ 18

和1< = n< = 10000

这里的每个值都是一个整数值

但我错了，但不知道在哪里



[edit]已添加代码块 - OriginalGriff [/ edit]

i am expecting to get correct answer for every value of x, n and a[i] where
-10^9 <= a[i] <= 10^9
1 <= x <= 10^18
and 1 <= n <= 10000
every value here is an integer value
but i am wrong somewhere but dont know where

[edit]Code block added - OriginalGriff[/edit]

推荐答案

1. 使用 nrt< break 2 。此中断与您的公式不符。第n个根渐近于1，而不是零。所以，你仍然必须根据你的公式添加这些术语。
2. n 永远不会被设置，但是在函数末尾读取 - 是什么 n 的含义？
3. 您的号码域名不清楚/损坏：您只计算整数（即丢弃根的任何部分）或做你用实数来计算 - 这会更有意义。你的公式没有提到整数。

1. Don't break with nrt < 2. This break is not in line with your formula. The n-th root goes asymptotic to 1, not to zero. So, you still must add these terms according to your formula.
2. n is never set, but read at the end of the function - what is the meaning of n?
3. Your number domains are unclear/broken: do you calculate with integral numbers only (i.e. discarding any fraction of the roots) or do you calcualte with real numbers - which would make more sense. Your formula nowhere mentions integral numbers.

仔细查看代码会显示一个混乱的实现：

- 函数内部使用的全局变量

- 未使用的rem数组（或者我错过了什么）

- 混淆代码 - 您的代码不会使标题中的公式失效



为什么不记下类似问题的代码？



例如在伪代码中：

Looking more closely into your code shows a confused implementation:
- global variables that are used inside the functions
- unused rem array (or am I missing something)
- obfuscated code - your code does not resemmble the formula in the title

Why don't you write down the code that resembles the problem?

E.g. in pseudo code:

read n, all n elements of array a
read q
foreach 1...q do
  read x
  y = solve(x, a, n)
  write y
end foreach

和函数求解函数

And the function solving function

function solve(x, a, n) returning y
do
   p = 1000000007
   y = 0;
   i = 0;
   while i is less than n do
     increment i by 1
     y = y + root(i, x) * a[i]
     y = y modulo p
   end while
   return y
end function

function root(i, x) returning r
do
   return i-th root of x // e.g. i-th root of x = floor(power(x, 1.0/i))
end function

这假定你的问题解决为整数域，即你的根总是向0舍入。用C / C ++实现并运行，然后才考虑优化（例如在早期阶段中断为不再对结果做出贡献的根 - 如果需要这样的优化...



[/编辑]



干杯

Andi

This assumes your problem solved as integer domain, i.e. your roots are always rounded towards 0. Get that implemented in C/C++ and running, and only then think about optimizing (e.g. like break at an early stage for roots that do not contribute anymore to the result - if such an optimization is needed at all...

[/EDIT]

Cheers
Andi

这篇关于计算错误（root（1，x）* A [1] + root（2，x）* A [2] + ... + root（N，x）* A [N]）％1000000007其中root（i ，x）是x的第i个根。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！