首页 > 代码库 > Uva 1069 Always an Integer ( 数学 )
Uva 1069 Always an Integer ( 数学 )
Uva 1069 Always an Integer ( 数学 )
#include <cstdio>#include <cstring>#include <algorithm>#include <cctype>using namespace std;typedef long long LL;#define MAXN 105#define CLR( a, b ) memset( a, b, sizeof(a) )LL c[ MAXN ], d;char str[ MAXN * MAXN ];void init(){ CLR( c, 0 ); LL k, a, key, sign = 1; d = k = a = key = 0; int len = strlen( str ); for( int i = 0; i <= len; ++i ) { if( isdigit( str[i] ) ) { if( key == 0 ) a = a * 10 + str[i] - ‘0‘; else if( key == 1 ) k = k * 10 + str[i] - ‘0‘; else if( key == 2 ) d = d * 10 + str[i] - ‘0‘; } else if( str[i] == ‘/‘ ) key = 2; else if( str[i] == ‘n‘ ) key = 1; else if( str[i] == ‘-‘ || str[i] == ‘+‘ || str[i] == ‘)‘ ) { if( key >= 1 ) { if( k == 0 ) k = 1; if( a == 0 ) a = 1; } c[k] = a * sign; if( str[i] == ‘-‘ ) sign = -1; else sign = 1; key = a = k = 0; } }}LL fast_mod( LL a, int b, LL MOD ){ LL ans = 1; while( b ) { if( b & 1 ) ans = ans * a % MOD; a = a * a % MOD; b >>= 1; } return ans;}bool judge(){ int n = MAXN - 1; while( c[n] == 0 ) n--; for( LL i = 1; i <= n + 1; ++i ) { LL ans = 0; for( int j = 0; j <= n; ++j ) { if( c[j] ) ans = ( ans + c[j] * fast_mod( i, j, d ) ) % d; ans = ( ans + d ) % d; } if( ans ) return false; } return true;}int main(){ int cas = 1; while( ~scanf( "%s", str) && strcmp( ".", str ) != 0 ) { init(); printf( "Case %d: %s\n", cas++, judge() ? "Always an integer" : "Not always an integer" ); } return 0; }
Uva 1069 Always an Integer ( 数学 )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。