bzoj 1968: [Ahoi2005]COMMON 约数研究 (思维题)

题目链接 题意：给出n+1个点，每次由i点到i+1点，每段线段之间保证不同向或者反向，第一个点和最后一个点保证重合。路径围成的封闭图形中间都是水，问有多少个危险点，使得如果在这个点忘记转弯就会掉进水里。

题目链接 题意： # For every pair of triplets, Ta = (Ia, Ja, Ka) and T__b = (Ib, Jb, Kb), we define the difference value between Ta and_T__b_ as follows: D(Ta,_ Tb_) = max {Ia − Ib, Ja − Jb, Ka − Kb} − min {Ia − Ib, Ja − Jb, Ka − Kb} Now you are given N triplets, could you write a program to calculate the sum of the difference values between every unordered pair of triplets?

题目链接 题意：求n！在k进制表示下有多少位。 思路：答案为[ log(1)+log(2)+…+log(N) ]+1 其中log的底数都是K 由于有多组数据，预处理一个log的前缀和。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :Tue 13 Sep 2016 05:13:15 PM CST 4File Name :code/loj/1045.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set>-digits-of-factorial-k进制数的位 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=1E6+7; 32int n; 33int base; 34double sum[N]; 35int main() 36{ 37 #ifndef ONLINE_JUDGE 38 freopen("code/in.txt","r",stdin); 39 #endif 40 sum[0] = 0 ; 41 for ( int i = 1 ; i < N ; i++) sum[i] = sum[i-1] + log(i); 42 int T; 43 cin>>T; 44 int cas = 0 ; 45 while (T--) 46 { 47 scanf("%d%d",&n,&base); 48 double ans = sum[n]/log(base)+1; 49 printf("Case %d: %d\n",++cas,int(ans)); 50 } 51 #ifndef ONLINE_JUDGE 52 fclose(stdin); 53 #endif 54 return 0; 55}

题目链接 题意：给出一个数，问包含这个数三个数组成的勾股数，输出另外两个数。 思路： 所谓勾股数，就是当组成一个直角三角形的三边长都为正整数时，我们就称这一组数为勾股数. 那么，组成一组勾股数的三个正整数之间，是否具有一定的规律可寻呢？下面我们一起来观察几组勾股数： 规律一：在勾股数（3,4,5）、（5,12,13）、（7,24,25）（9,40,41）中，我们发现 由（3,4,5）有：32=9=4+5 由（5,12,13）有：52=25=12+13 由（7,24,25）有：72=49=24+25 由（9,40,41）有：92=81=40+41. 即在一组勾股数中，当最小边为奇数时，它的平方刚好等于另外两个连续的正整数之和.因此，我们把它推广到一般，从而可得出以下公式： ∵（2n+1)²=4n²+4n+1=（2n²+2n）+（2n²+2n+1） ∴（2n+1)²+（2n²+2n)²=（2n²+2n+1)²（n为正整数） 证明（略） 勾股数公式一：（2n+1,2n²+2n,2n²+2n+1）（n为正整数） 规律二：在勾股数（6,8,10）、（8,15,17）、（10,24,26）中，我们发现 由（6,8,10）有：62=36+2×（8+10） 由（8,15,17）有：82=64=2×（15+17） 由（10,24,26）有：102=100=2×（24+26） 即在一组勾股数中，当最小边为偶数时，它的平方刚好等于两个连续整数之和的二倍，推广到一般，从而可得出另一公式： ∵（2n）2=4n2=2[（n2-1）+（n2+1）] ∴（2n）2+（n2-1）2=（n2+1）2（n≥2且n为正整数） 证明（略） 勾股数公式二：（2n,n²-1,n²+1）（n≥2且n为正整数） 利用以上两个公式，我们可以快速写出各组勾股数.

hdu 5833 题目链接 题意：n个数，保证每个数的素因子不超过2000，从中取若干个，问乘积是完全平方数的方案数。 思路： 完全平方数就是要求每个质因子的指数是偶数次。 列方程组，a1,a2,a3……am分别表示bi是否在集合中。对于每一个素因子，建立异或方程组，要求因子个数为偶数，即异或为0