反素数学习笔记

题目链接 题意：给出n个数，m个查询，每组查询一个区间[l,r]，问[l,r]中会被吃掉多少个（区间[l,r]中的数只有当其是其他所有数的因数时才不会被吃掉，顺便问一句。。a divide b 是 a除b，也就是b除以a,b/a的意思嘛23333）

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 的数有多少个。