UVA-10710 Skyscraper Floors （找规律+幂取模）

题目大意：题目中给了一种数的定义，根据定义，让判断一个给定的数是不是这种数。题中叫这种数为吉米数，定义如下：对序列1,2,3，，，，n，做n-1次SF变换（对该变换的解释在下文），如果能得到原序列，则n为吉米数。

SF变换：若n为偶数，以n=10为例，一次SF变换是这样的

　　　　1,2,3,4,5,6,7,8,9,10—>1,2,3,4,5　　6,7,8,9,10—>6,1,7,2,8,3,9,4,10,5　　此为偶数的一次SF变换，第二次变换是基于新序列的，以此类推。

　　　　若n为奇数，以n=9为例，一次SF变换是这样的

　　　　1,2,3,4,5,6,7,8,9—>1,2,3,4　　5,6,7,8,9—>5,1,6,2,7,3,8,4,9　　　此为奇数的一次SF变换，第二次变换也是基于新序列的，以此类推。

题目分析：根据题中的提示，偶数不是吉米数。如果是吉米数，则相应的序列中的任一元素的位置周期都是一样的，所以只需考虑1。最终找到1的位置有如下规律：pos=(2^t)%n，其中t为变换的次数。所以只需判断(2^(n-1))%n=1是否成立即可。

实际上还是幂取模！！！

代码如下：

 # include<iostream>

 # include<cstdio>

 # include<cstring>

 # include<algorithm>

 using namespace std;

 # define ll long long

 ll mypow(ll a,ll b,ll m)

 {

     if(b==)

         return ;

     if(b==)

         return a%m;

     ll u=mypow(a,b/,m);

     u*=u;

     u%=m;

     if(b&)

         u*=a;

     return u%m;

 }

 bool is(ll x)

 {

     ll pos=mypow(,x-,x);

     return pos==;

 }

 int main()

 {

     ll n;

     while(scanf("%lld",&n)&&n!=-){

         if(is(n))

             printf("%lld is a Jimmy-number\n",n);

         else

             printf("%lld is not a Jimmy-number\n",n);

     }

     return ;

 }

巴特西

UVA-10710 Skyscraper Floors （找规律+幂取模）

最新文章

热门文章