英文:
Product of N numbers, incorrect answer, possible overflow?
问题
我正在尝试解决问题“前n个数字的乘积”。
long ans=1;
for(int i=1;i<=n;i++){
ans = ans*i;
}
return ans % (1000000007) ;
对于较大的n，我得到了不正确的结果，我怀疑可能发生了溢出。我应该如何解决这个问题？
英文:
I am trying to solve the problem "product of first n numbers"
long ans=1;
for(int i=1;i<=n;i++){
ans = ans*i;
}
return ans % (1000000007) ;
I am incorrect result for large n, I suspect possible overflow. How do I go about solving it?
答案1
得分: 5
如果你需要写 `answer % 1000000007`，你可以（我猜你应该）在每次 `for` 循环中都使用 `%` 运算符。
long ans = 1;
long p = 1000000007;
for (int i = 0; i < n; i++)
{
ans = (ans * i) % p;
}
return ans;
如果这还不够，你可以尝试这样做：
long ans = 1;
long p = 1000000007;
for (int i = 0; i < n; i++)
{
ans = ((ans % p) * (i % p)) % p;
}
return ans;
英文:
If you have to write answer % 1000000007, you can (and I guess you should) use % operator every time in for loop.
long ans = 1;
long p = 1000000007;
for (int i = 0; i < n; i++)
{
ans = (ans * i) % p;
}
return ans;
If this is not enough, you can try this:
long ans = 1;
long p = 1000000007;
for (int i = 0; i < n; i++)
{
ans = ((ans % p) * (i % p)) % p;
}
return ans;
答案2
得分: 0
这里是 BigInteger 解法：
int p = 1_000_000_007;
BigInteger fact = BigInteger.TWO;
int N = 50;
for (int i = 3; i < N; i++) {
fact = fact.multiply(BigInteger.valueOf(i));
}
System.out.println(fact.mod(BigInteger.valueOf(p)));
打印结果：
726372166
要在不使用 BigInteger 的情况下解决此问题，可以使用以下关系式：
(a mod n) * (b mod n) = ab mod n.
可以适用于更大范围的整数，可以这样做：
long mod = 2;
int N = 50;
for (int i = 3; i < N; i++) {
mod = (mod * i) % p;
}
System.out.println(mod);
打印结果：
726372166
注意：1_000_000_007 是一个素数，因此可以确保任何产品都不会将该值作为因子。如果 N >= p，则所有后续结果都将为 0，即使首先使用 BigInteger 计算产品，因为当产品被 p 除时，余数将为零。
英文:
First, here is the BigInteger solution.
int p = 1_000_000_007;
BigInteger fact = BigInteger.TWO;
int N = 50;
for (int i = 3 ;i < N; i++) {
fact = fact.multiply(BigInteger.valueOf(i));
}
System.out.println(fact.mod(BigInteger.valueOf(p)));
prints
726372166
To solve this without using BigInteger, one can use the relationship that says that
(a mod n) * (b mod n) = ab mod n.
Check out the proof here
Since the above can be applied to a larger range of integers, one can do the following:
long mod = 2;
int N = 50;
for (int i = 3; i < N; i++) {
mod = (mod * i) % p;
}
System.out.println(mod);
prints
726372166
Note: 1_000_000_007 is a prime number and thus guarantees no product above will ever have that value as a factor. If N >= p then all subsequent results will be 0, even if the product is first computed using BigInteger, because the remainder will be zero when the product is divided by p
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论