数论

hdu 2853 题目链接 题意：n 个公司，m 个任务（m>=n)，一个公司只能对应一个任务，一个任务也只能对应一个公司。给出一个 n*m 的 mat，表示每个公司对应每个任务产生的 val。然后给出 n 个数，表示初始钦定（雾）这 n 个公司分别做哪些任务。但是可能初始的安排得到的 val 不是最大的。我们现在想得到最大的 val，并且保证改变的安排数最少。求安排后得到的 val 比初始安排大多少，以及需要改变的安排数量。

http://poj.org/problem?id=2356 题意：有 n 个数，从中选取若干个（1..n），和能被 n 整除。问是否有解，无解输出 0，有解的话，输出个数以及选择的 a[i]（不是 i）。 由抽屉原理可知一定有解： 做一个带模的前缀和 sum[i]=(sum[i-1]+a[i])%n n个数，sum[i]最多有n种。 如果某个sum[i]为0，那么表示从1到i的和能被n整除。 如果所有的 sum[i] 不为 0，那么一共有 n 个 sum[i]、n-1 个值（1..n-1），一定有 sum[i] == sum[j]（i <= j）。 那么a[i]到a[j]的和一定能被n整除。

http://acm.nyist.net/JudgeOnline/problem.php?pid=509 题意：中文题目。。。 思路：快速筛即可。。。妈蛋。。。这个oj不能用宏编译==。。。然后一直TLE…去掉了就好了。。sad 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年01月20日 星期三 13时53分54秒 4File Name :code/nyoj/509.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=10500; 34int n; 35int pri[N]={0}; 36int npri[N]={1,1}; 37int num[N]; 38int cnt; 39 40void pre() 41{ 42 cnt = 0 ; 43 for ( int i = 2 ; i < N ; i++) 44 { 45 if (!npri[i]) pri[cnt++] = i; 46 47 for ( int j = 0 ; j < cnt &&i*pri[j]<N ;j++) 48 { 49 npri[i*pri[j]] = 1; 50 if (!(i%pri[j])) break; 51 52 } 53 54 } 55// for ( int i = 0 ; i <= 100 ; i++) printf("%d ",pri[i]); 56 57} 58void solve ( int x) 59{ 60 for ( int i = 2 ; i <= x ; i++) 61 { 62 int tmp = i; 63 for ( int j = 0 ; j < cnt ; j++) 64 { 65 while (tmp%pri[j]==0) 66 { 67 tmp/=pri[j]; 68 num[j]++; 69 70 } 71 if (tmp==1) break; 72 } 73 } 74 for ( int i = 0 ; i < cnt ; i++) 75 { 76 if (pri[i]>x) break; 77 printf("%d ",num[i]); 78 } 79} 80int main() 81{ 82 #ifndef ONLINE_JUDGE 83// freopen("code/in.txt","r",stdin); 84 #endif 85 86 pre(); 87 int T; 88 cin>>T; 89 while (T--) 90 { 91 ms(num,0); 92 scanf("%d",&n); 93 solve(n); 94 puts(""); 95 } 96 97 #ifndef ONLINE_JUDGE 98 fclose(stdin); 99 #endif 100 return 0; 101}

http://codeforces.com/contest/611/problem/B 题意：问a到b（1E18），二进制表示中只有一个0的数有多少个。 思路：这么大的数。。。不是有循环节就是math problems. UD:20160318讲道理还有可能是数位dp好不好。。。 我们发现可以很容易得算出1到x的二进制表示中只有一个0 的数有多少个。

http://codeforces.com/contest/16/problem/C 题意：给定长宽a,b和分辨率x:y，注意分辨率x:y未必是最简比。问将现有的size裁剪成比例为x:y，使得面积最大的长宽是多少。 思路：可以通过找 x,y能扩大的倍数为k，找到一个最大的k使得kx<=a&&ky<=b。可以二分搞，但其实也可以不用。能扩大的最大的倍数其实就是 min(a/x,b/y). ps：收获了gcd更简单的一种写法。 直接 return b?gcd(b,a%b):a;

1106 质数检测 基准时间限制：1 秒 空间限制：131072 KB 分值： 0 难度：基础题 收藏 关注 给出N个正整数，检测每个数是否为质数。如果是，输出"Yes"，否则输出"No"。

水题 写一遍的目的是。。。复习一下快速筛的写法　喵呜 代码实现 1/************************************************************************* 2 > File Name: code/poj/2909.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年08月22日 星期六 14时25分34秒 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#define y0 abc111qqz 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define tm crazy111qqz 25#define lr dying111qqz 26using namespace std; 27#define REP(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef unsigned long long ULL; 30const int inf = 0x3f3f3f3f; 31const int N=1<<16; 32bool not_prime[N]; 33int prime[N]; 34int prime_num; 35int n; 36 37void init(){ 38 not_prime[0] = true; 39 not_prime[1] = true; 40 for ( int i =2 ; i < N ; i++){ 41 if (!not_prime[i]){ 42 prime[++prime_num] = i; 43 } 44 for ( int j = 1 ; j <= prime_num&&i*prime[j]<N ; j++){ 45 not_prime[i*prime[j]] = true; 46 if (i%prime[j]==0) break; 47 } 48 } 49} 50int main() 51{ 52 init(); 53 int n ; 54 while (scanf("%d",&n)&&n){ 55 int ans = 0 ; 56 for ( int i = 2 ; i <= n /2 ; i++){ 57 if (!not_prime[i]&&!not_prime[n-i]){ 58 ans++; 59 } 60 } 61 printf("%d\n",ans); 62 } 63 64 return 0; 65}

题意是说，能构造多少本元勾股数和勾股数，要求构造的数<=n 所谓本元勾股数，就是三个勾股数没有公因数，两两互质。 由本元勾股数扩大k倍，就可以得到其他勾股数。 而构造本元勾股数的方法如下：

转载自：http://www.cnblogs.com/vongang/archive/2013/03/10/2952978.html POJ【数论/组合/博弈论】题目列表

昨天那道签到的数学题没搞出来不开心. 是时候刷一波数学了 这题题意是说，从n个数中任选m个，使得m个的和为c的倍数. 如果有解，输出选的数的下标，否则输出无解字符串. 抽屉原理的原始描述是，如果有n+1个物品，有n个抽屉，那么至少有一个抽屉有2个物品.

TAG 素数 数论 素数总是一个比较常涉及到的内容，掌握求素数的方法是一项基本功。 基本原则就是题目如果只需要判断少量数字是否为素数，直接枚举因子 2 到 N^(0.5)，看看能否整除 N。

它有一定的规律性，排列如下(构成图)，像上面的1、3、6、10、15等等这些能够表示成三角形的形状的总数量的数，叫做三角形数。 一定数目的点或圆在等距离的排列下可以形成一个等边三角形，这样的数被称为三角形数。比如10个点可以组成一个等边三角形，因此10是一个三角形数：

ACM STEPS里的…这题前面一道是求LCM….结果接下来就是这么一道。。。 朴素会超….筛法会爆….题目顺序真是按照难度来的？ 于是想到 Miller-Rabin素数测试……. 这个方法是基于费马小定理 我的理解就是… 如果我要判断n是否为素数 只要取k个数 如果满足 a^(n-1)mod n =1 那么n就很可能为素数。 证明什么的…暂时还是算了吧…论文里貌似扯了一大堆 第一次用，竟然真的A了。。。。 感觉更好的办法也许是先打一个比较小的素数表，然后每次random选取若干个进行判断…那样应该更可靠些？ 本来想WA掉之后再改的。。。没想到这么写就A掉了。。。。杭电数据略水？