本文主要是介绍2014年暑假培训 - 数论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A银河上的星星
/**************************************************************
Problem: 1014
User: DoubleQ
Language: C++
Result: Accepted
Time:190 ms
Memory:1688 kb
****************************************************************/
两直角边的最大公约数-1。最后的-1操作这样理解，一条直线上四个点把直线分
成5块，我们所求的最大公约数就是这5块，减1就得到直线上的点数。*/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b , a % b);
}
int main()
{//freopen("in.txt","r",stdin);
int m , n , x , y;
while(~scanf("%d%d%d%d",&m ,&n, &x ,&y))
{
int a = abs(m - x);
int b = abs(n - y);
int t;
if(a < b)
{
t = a;
a = b;
b = t;
}
printf("%d\n",gcd(a, b) - 1);
}
}
C: 素数判定
/**************************************************************
Problem: 1054
User: DoubleQ
Language: C++
Result: Accepted
Time:531 ms
Memory:1688 kb
****************************************************************/
/*如果n小于等于1的话，直接输出NO；否则应用素数基本判别法，从2到sqrt(n)开始遍历，若发现n % i == 0,
则说明n是合数，否则，n是素数。*/
/*基本素数判别法：如果n是一个合数，那么n一定有一个不超过sqrt(n)的素因子*/
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std; //int pri[46000] , npri; int n; void solve( int n) { if (n == 0) printf ( "NO\n" ); else if (n == 1) printf ( "NO\n" ); else { int flag = 0; for ( int i = 2 ; i * i <= n ;i ++) if (n % i == 0) { flag=1; printf ( "NO\n" ); break ; } if (!flag) printf ( "YES\n" ); } } int main() { //freopen("in.txt","r",stdin); while (~ scanf ( "%d" ,&n)) { solve(n); } } D: 因式分解
/************************************************************** Problem: 1058 User: DoubleQ Language: C++ Result: Accepted Time:579 ms Memory:5600 kb ****************************************************************/
/*分解质因数，对n进行质因数分解，若n为1，则直接输出1；否则用数组a来存n的所有因子。
每次都找到一个最小的质因数i : (1)如果i== num，说明质因数分解过程已结束，直接return；
（2）若num>i,并且num可以整除i，把num用num/i的商重置，重复第一步；（3）若num不
能整除i ， 则i++,重复第一步。*/
#include <iostream> #include <cstdio> using namespace std; int a[1000010]; void solve( int num , int &na) { int t = num; for ( int i = 2; i <= num; i++) { while (1) { //cout << "hello" << endl; if (t == i) { a[na++] = i; return ; } else if (t % i == 0) { a[na++] = i; t /= i; } else break ; } } } int main() { //freopen("in.txt","r",stdin); int n; while (~ scanf ( "%d" ,&n)) { if (n == 1) { printf ( "1 = 1\n" ); continue ; } int na = 0; solve(n, na); printf ( "%d = " ,n); for ( int i = 0 ; i < na - 1; i ++) printf ( "%d * " , a[i]); printf ( "%d\n" ,a[na-1]); } } E: Fibonacci Again
/************************************************************** Problem: 1059 User: DoubleQ Language: C++ Result: Accepted Time:29 ms Memory:5600 kb ****************************************************************/
/*f(n) = (f(n-1) %3 + f(n-2) % 3) %3,直接打表*/
#include <iostream> #include <cstdio> using namespace std; #define N 1000011 int d[N]; void pre_solve() { d[0] = 7 % 3 ,d[1] = 11 % 3; for ( int i = 2; i <= 1000000; i++) d[i] = (d[i-1]%3 + d[i-2]%3) %3;
} int main() { pre_solve(); int n; while (~ scanf ( "%d" ,&n)) { if (!d[n]) printf ( "yes\n" ); else printf ( "no\n" ); } } G: 双六简化版
/************************************************************** Problem: 1062 User: DoubleQ Language: C++ Result: Accepted Time:1 ms Memory:1692 kb ****************************************************************/
/*扩展欧几里得模板，最后判断有无解，就是得出来的gcd是否的1 */
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int exgcd( int a , int b , int &x, int &y) { if (b == 0) { x = 1 ; y = 0 ; return a; } int r = exgcd(b , a % b , x , y); int t = y ; y = x - (a / b) * y; x = t; return r; } int main() { //freopen("in.txt","r",stdin); int a, b , x, y; while (~ scanf ( "%d%d" ,&a, &b)) { int k = exgcd(a , b ,x, y); if (k != 1) printf ( "-1\n" ); else cout << x << " " << y << endl; } } 这篇关于2014年暑假培训 - 数论的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
