题解 1375: NEW RDSP MODE I

解题思路:

    这题是一个智力题。

    首先我们数组下标从1开始计算（为了方便理解），第一个数字为a[1]

    现在我们看n=500，m=1，x=500的情形（我们把数组所有元素都考虑到，用一个统一的数学运算来代替题目中的乱七八糟的运算）

    初始状态是1...500

    进行了第一次处理后的数组变成了2,4,6,...500,1,3....499

    对于前250个数字，与未处理时相比，处理后变为了原先的2倍。

那么我们可不可以通过一个%取模运算，让后面的奇数与前面的值进行统一呢？

考虑到a[250]=500,a[251]=1，我们只需要找到一个数字model，使得(251*2)%model=1，那么后面的奇数是不是就与前面统一了？

所以我们显而易见，找到了，答案是n+1，(251*2)%501=1。

所以我们找到了统一的，处理完后的数组内的一个数学运算。对于前i个数而言，答案就是(2^m*i)%(n+1)。

还没完，这是n是偶数的情形。

n是奇数时，我们找到的这个model的值是不同的。

n=7时，进行第一次处理后，序列是2,4,6,1,3,5,7，model的值为7。（第7个数要注意处理一下，%运算会变为0。奇数这里要注意最后一个数字的问题）

故我们会区分n的奇偶性来选不同的model值，奇数时第i个数的答案是(2^m*i)%n

现在我们已经得到了一个结论，用乱七八糟的方式处理数组等价于上述式子的取模运算。

注意事项:

现在m的值是10^9，n的值是10^6，所以我们在2^m的运算过程中使用快速幂并记得随时取模，但是要注意，因为n<10^6，int的运算会爆范围，所以要采用long long。


参考代码:

#includeusing namespace std; 
long long n,m,x,temp,model,tx,ans,i;
long long setout(long long Num){
    Num=Num%model;
    if(Num==0)return n;
    return Num;
}

int main()
{
  
    while(cin>>n>>m>>x){
        model=n;
        if(model%2==0)model++;
        temp=2;ans=1;
        while(m>0){
            if(m%2){
                ans=(ans*temp)%model;
            }
            temp=(temp*temp)%model;
            m/=2;
        }
        
        cout<<setout(ans);
        for(i=2;i<=x;i++)
        cout<<' '<<setout(ans*i);
        cout<<endl;
    }
    return 0;
}