X-Sequence

超、凢脫俗 2022-08-22 13:23 22阅读 0赞

181. X-Sequence

time limit per test: 0.25 sec.

memory limit per test: 4096 KB

input: standard

### output: standard ###

Let \{x i\} be the infinite sequence of integers:  
1) x 0 = A;  
2) x i = (alpha \* x i-1^2 + beta \* x i-1 + gamma) mod M, for i >= 1.  
Your task is to find x k if you know A, alpha, beta, gamma, M and k.

### Input ###

Given A (1 <= A <= 10000), alpha (0 <= alpha <= 100), beta (0 <= beta <= 100), gamma (0 <= gamma <= 100), M (1 <= M <= 1000), k (0 <= k <= 10^9). All numbers are integer.

###    Output ###

Write x k.  
  
Sample test(s)

###    Input ###

1 1 1 1 10 1

### Output ###

1，查找循环节。考虑特殊的不是从第一位开始循环的情况（9,8,5,4,3,5,4,3,5,4,3）//从第3位开始循环，循环节为3，循环数字为5.4.3

#include<stdio.h>  
    #include<string.h>  
    int main()  
    {  
        int A, alpha, beta, gamma, M , k;  
        int loop,i,t;  
        int num[1010];  
        int visit[10100];  //visit用来标记是否num[i]的值是否出现过即visit[num[i]]是否是-1   
        while(~scanf("%d%d%d%d%d%d",&A,&alpha,&beta,&gamma,&M,&k))  
        {  
              
            memset(visit,-1,sizeof(visit));  
            num[0]=A;visit[A]=0;  
            for(i=1;;i++)  
            {  
                num[i]=alpha*num[i-1]%M*num[i-1]%M+beta*num[i-1]%M+gamma%M;  
                num[i]%=M;  
                if(visit[num[i]]!=-1)
    			{  
                    loop=i-visit[num[i]]; //这样loop正好为循环个数  
                    t=visit[num[i]];//表示循环列前面还有的个数  
                    break;  
                }  
                else visit[num[i]]=i;  
              
            }  
            if(k<visit[num[i]]) 
    		printf("%d\n",num[k]); //如果k未出现循环  
            else
    		 printf("%d\n",num[(k-t)%loop+t]); //出现循环节，只需计算属于循环的哪一个数      
        }  
        return 0;  
    }

X-Sequence

发表评论取消回复

还没有评论，来说两句吧...

相关阅读