传送门:Codeforces Round #276 (Div. 2)
按照题目规则改变a,a大于m时没意义,所以对m取模,根据题意,当a变化时变回到以前出现过的a时,说明出现循环,无解,否则会一直进行到出现a%m==0为止。
#include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std ; typedef long long LL ; #define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i ) #define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i ) #define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next ) #define clr( a , x ) memset ( a , x , sizeof a ) const int MAXN = 100005 ; int vis[MAXN] ; int a , m ; void solve () { clr ( vis , 0 ) ; int ok = 0 ; while ( 1 ) { if ( a % m == 0 ) { ok = 1 ; break ; } else if ( vis[a % m] ) break ; vis[a % m] = 1 ; a = ( a + a % m ) % m ; } printf ( ok ? "Yes\n" : "No\n" ) ; } int main () { while ( ~scanf ( "%d%d" , &a , &m ) ) solve () ; return 0 ; }
ans = max(maxx - minx , maxy - miny )^ 2。
#include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std ; typedef long long LL ; #define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i ) #define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i ) #define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next ) #define clr( a , x ) memset ( a , x , sizeof a ) const int INF = 0x3f3f3f3f ; int n ; void solve () { LL minx = INF , miny = INF ; LL maxx = -INF , maxy = -INF ; LL x , y ; For ( i , 1 , n ) { scanf ( "%I64d%I64d" , &x , &y ) ; minx = min ( minx , x ) ; maxx = max ( maxx , x ) ; miny = min ( miny , y ) ; maxy = max ( maxy , y ) ; } LL ans = max ( maxx - minx , maxy - miny ) ; printf ( "%I64d\n" , ans * ans ) ; } int main () { while ( ~scanf ( "%d" , &n ) ) solve () ; return 0 ; }
从l的最低位开始每位挨个填1直到l>r为止,这样一定是1个数最多的且最小的,比这个1多的肯定不存在,剩下的都是比他大的。
#include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std ; typedef long long LL ; #define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i ) #define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i ) #define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next ) #define clr( a , x ) memset ( a , x , sizeof a ) LL l , r ; int n ; void solve () { scanf ( "%I64d%I64d" , &l , &r ) ; //LL ans = 0 ; rep ( i , 0 , 63 ) { if ( ( l | ( 1LL << i ) ) <= r ) { l |= ( 1LL << i ) ; } } printf ( "%I64d\n" , l ) ; } int main () { int T ; scanf ( "%d" , &T ) ; while ( T -- ) solve () ; return 0 ; }
我们可以对每个数ai的所有倍数,找从左端靠近的最接近这个倍数的数aj,同时要满足aj>ai,然后更新ans = max (ans,aj%ai)。
我们可以预处理出1~2000000内每个数x从左端靠近的最接近这个数的数,类似递推:
nearest[i] = hash[i - 1] ? i - 1 : nearest[i - 1]。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; #define rep( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define For( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define rev( i , a , b ) for ( int i = a ; i >= b ; -- i ) #define clr( a , x ) memset ( a , x , sizeof a ) const int MAXN = 1000005 ; int nearest[MAXN << 1] ; bool hash[MAXN << 1] ; int n ; void solve () { int x , ans = 0 ; clr ( hash , 0 ) ; clr ( nearest , 0 ) ; For ( i , 1 , n ) { scanf ( "%d" , &x ) ; hash[x] = 1 ; } For ( i , 1 , 2000000 ) { if ( hash[i - 1] ) nearest[i] = i - 1 ; else nearest[i] = nearest[i - 1] ; } For ( i , 2 , 1000000 ) if ( hash[i] && ans < i - 1 ) { for ( int j = i + i ; j < 1000000 + i ; j += i ) { if ( nearest[j] > i ) { ans = max ( ans , nearest[j] % i ) ; if ( ans == i - 1 ) break ; } } } printf ( "%d\n" , ans ) ; } int main () { while ( ~scanf ( "%d" , &n ) ) solve () ; return 0 ; }