时间戳

首页 > 解决方案 > 给定整数 n,d,i [ n*d + (id) ]%n 等价于 [n + (id)]%n？(% c++ 取模)

c++ - 给定整数 n,d,i [ n*d + (id) ]%n 等价于 [n + (id)]%n？(% c++ 取模)

问题描述

Given range of n :[0, 10^5]
..........range of d :[1,n]
..........range of i :[0,n]

使用上述参数及其给定范围。
我假设 (n*d + id )%n 等价于 (n + id )%n。
考虑一个对 n 个元素数组/向量执行 d 左旋转并返回包含输入数组/向量的旋转输出的数组/向量的函数。

下面的这个 c++ 函数可以正常工作并产生正确的答案。

vector<int> rotLeft_1(vector<int> a, int d) 
{
    int n = a.size();
    vector<int> ans(n,0);
    for(int i=0; i<n; i++)
    {
        answer[(n + i-d)%n] = a[i];
    }
    return answer;
}

下面的这个 c++ 函数不适用于较大的 n 和 d 值。IE。n = 73642，d = 60581。如，下面的函数有时会产生分段错误错误。

vector<int> rotLeft_2(vector<int> a, int d) 
{
    int n = a.size();
    vector<int> ans(n,0);
    for(int i=0; i<n; i++)
    {
        answer[(n*d + i-d)%n] = a[i];
    }
    return answer;
}

现在的问题是，我的假设 (n*d + id )%n 等于 (n + id )%n 错误吗？
还是这里有更多的游戏？非常感谢。

标签： c++arraysalgorithm

解决方案

使用 n*d 你会溢出INT_MAX。

int 类型变量的最大值。2147483647

因此，由于溢出，您的 n*d 值变为负数，然后您尝试访问导致段错误的数组的负索引。

解决方案：如果您在之后立即使用模 n，我看不出有 n*d 的意义，这样您就可以避免乘以 d。

如上所述，n 也不会超过 100000。

推荐阅读