数学 – Page 2 – hahaschool

POJ 3090 Visible Lattice Points

August 22, 20152015-08-22hahaschoolLeave a comment

题意

给出了一个1001×1001的点阵，和查询q，你要求出从(0,0)点到(q,q)点有多少种不同的点到原点的斜率（也就是题目中所说的“可见”），原点到原点不算。

思路

很直接的就可以想到算出所有的点到原点的斜率，预处理出答案，我们的做法是：从原点开始，一圈一圈地向外扩张，对于每个点都计算一边斜率，然后确认该斜率是否出现过，没出现过的话，当前圈上的点到原点的不同的斜率个数+1，这样求出每一圈的数目，最后我们再求一个前缀和就好了。

时间很理想，是O(n^2*log(n))的，然而POJ上超时了。我拿到ideone上测速，是700ms，可以过的，可能是评测机不在状态吧ˊ_>ˋ。补救的方法就是打了个表，反正数据也很少。

然而这个题的精髓并不是这么水过去的，这个题其实是一个包装过了的法雷级数(Wikipedia::法里数列可能需要科学上网)，如果试着一圈圈地写一下斜率，就会发现每一圈正好满足分子和分母互质的特性，每一圈的个数其实是欧拉函数值，整个答案是欧拉函数前缀和。所以我们就有了O(n)，的处理方法，详细的可以看这个题POJ 2478 Farey Sequence。

明明是刚做过的题居然都没有反应过来看来我真的是太迟钝了呢。

代码(暴力解法)

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

struct Fac{
    int up;
    int down;
    int gcd(int a,int b){
        if (b == 0) {
            return a;
        }
        return gcd(b, a%b);
    }
    void reduce(){
        int _gcd = gcd(up, down);
        up /= _gcd;
        down /= _gcd;
    }
    friend bool operator < (Fac a,Fac b){
        if(a.up == b.up){
            return a.down < b.down;
        }else
            return a.up < b.up;
    }
};

Fac tg(int x,int y){
    Fac ret;
    ret.up = y;
    ret.down = x;
    ret.reduce();
    return ret;
}

set<Fac> vis;
int ans[1001];

void get_ans(){
    for (int i = 1; i <= 1000; i++) {
        int x = 0, y = i;
        for (x = 0; x <= i; x++) {
            Fac _tg = tg(x, y);
            if (!vis.count(_tg)) {
                vis.insert(_tg);
                ans[i]++;
            }
        }
        x = i;
        for (y = i-1; y >= 0; y--) {
            Fac _tg = tg(x, y);
            if (!vis.count(_tg)) {
                vis.insert(_tg);
                ans[i]++;
            }
        }
        ans[i] += ans[i-1];
    }
}

int main(){
    get_ans();
    int caseCnt;
    scanf(" %d",&caseCnt);
    for (int d = 1; d <= caseCnt; d++) {
        int q;
        scanf(" %d",&q);
        printf("%d %d %d\n",d,q,ans[q]);
    }
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

struct Fac{

int up;

int down;

int gcd(int a,int b){

if (b == 0) {

return a;

}

return gcd(b, a%b);

}

void reduce(){

int _gcd = gcd(up, down);

up /= _gcd;

down /= _gcd;

}

friend bool operator < (Fac a,Fac b){

if(a.up == b.up){

return a.down < b.down;

}else

return a.up < b.up;

}

};

Fac tg(int x,int y){

Fac ret;

ret.up = y;

ret.down = x;

ret.reduce();

return ret;

}

set<Fac> vis;

int ans[1001];

void get_ans(){

for (int i = 1; i <= 1000; i++) {

int x = 0, y = i;

for (x = 0; x <= i; x++) {

Fac _tg = tg(x, y);

if (!vis.count(_tg)) {

vis.insert(_tg);

ans[i]++;

}

x = i;

for (y = i-1; y >= 0; y--) {

Fac _tg = tg(x, y);

if (!vis.count(_tg)) {

vis.insert(_tg);

ans[i]++;

}

ans[i] += ans[i-1];

}

int main(){

get_ans();

int caseCnt;

scanf(" %d",&caseCnt);

for (int d = 1; d <= caseCnt; d++) {

int q;

scanf(" %d",&q);

printf("%d %d %d\n",d,q,ans[q]);

}

POJ 2478 Farey Sequence

August 21, 20152015-08-21hahaschoolOne Comment

题意

介绍性的问题，法雷级数(Wikipedia::法里數列可能需要科学上网)。

简单暴力，给出一个n，求出对于1～n中每一个数，有多少个小于等于他的数与他互质，把这些数量加在一起是多少，其实就是求欧拉函数的前缀和。

思路

欧拉函数有两种得到的方法，一是使用分解因子的方法，得到单个数的欧拉函数值，时间复杂度O(sqrt(n) * log(n))。如下：

//only for single number circumstances
long long s_phi(long long n)
{
    long long m=(long long)sqrt(n+0.5),ans=n;
    for(long long i=2;i<=m;i++)
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}

//only for single number circumstances

long long s_phi(long long n)

{

long long m=(long long)sqrt(n+0.5),ans=n;

for(long long i=2;i<=m;i++)

{

if(n%i==0)

{

ans=ans/i*(i-1);

while(n%i==0)n/=i;

}

if(n>1)ans=ans/n*(n-1);

return ans;

}

可以发现这样算的话如果只求一个数的欧拉函数还是不亏的，但是如果要求非常非常多的欧拉函数，时间就会爆炸，所以我们不可以在这个题用这种方法。

第二种方法是利用欧拉函数的若干性质：欧拉函数线性筛法详解(Lytning)，然后把素数的线性筛法和求欧拉函数结合到一起，如果要求非常多的欧拉函数，使用这种方法预处理是非常快的，而且还顺便求了素数，一石二鸟。

const int N = 1000000;
int n;
int phi[N+10],prime[N+10],tot,ans;//phi储存的是欧拉函数 prime按次序保存了全部的素数 mark是素数标记，false意味素，true意味合
bool mark[N+10];
void getphi()
{
    int i,j;
    phi[1]=1;
    for(i=2;i<=N;i++)//相当于分解质因式的逆过程
    {
        if(!mark[i])
        {
            prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。
            phi[i]=i-1;//当 i 是素数时 phi[i]=i-1
        }
        for(j=1;j<=tot;j++)
        {
            if(i*prime[j]>N)  break;
            mark[i*prime[j]]=1;//确定i*prime[j]不是素数
            if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数
            {
                phi[i*prime[j]]=phi[i]*prime[j];break;
            }
            else  phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性
        }
    }
}

const int N = 1000000;

int n;

int phi[N+10],prime[N+10],tot,ans;//phi储存的是欧拉函数 prime按次序保存了全部的素数 mark是素数标记，false意味素，true意味合

bool mark[N+10];

void getphi()

{

int i,j;

phi[1]=1;

for(i=2;i<=N;i++)//相当于分解质因式的逆过程

{

if(!mark[i])

{

prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。

phi[i]=i-1;//当 i 是素数时 phi[i]=i-1

}

for(j=1;j<=tot;j++)

{

if(i*prime[j]>N) break;

mark[i*prime[j]]=1;//确定i*prime[j]不是素数

if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数

{

phi[i*prime[j]]=phi[i]*prime[j];break;

}

else phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性

}

快速地得到欧拉函数值之后，前缀和什么的就是很简单的事情了。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

const int N = 1000000;
int n;
int phi[N+10],prime[N+10],tot,ans;//phi储存的是欧拉函数 prime按次序保存了全部的素数 mark是素数标记，false意味素，true意味合
bool mark[N+10];
void getphi()
{
    int i,j;
    phi[1]=1;
    for(i=2;i<=N;i++)//相当于分解质因式的逆过程
    {
        if(!mark[i])
        {
            prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。
            phi[i]=i-1;//当 i 是素数时 phi[i]=i-1
        }
        for(j=1;j<=tot;j++)
        {
            if(i*prime[j]>N)  break;
            mark[i*prime[j]]=1;//确定i*prime[j]不是素数
            if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数
            {
                phi[i*prime[j]]=phi[i]*prime[j];break;
            }
            else  phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性
        }
    }
}

long long phisum[1000006];

int main(){
    getphi();
    for (int i = 2; i <= 1000000; i++) {
        phisum[i] = phi[i] + phisum[i-1];
    }
    int q;
    while (cin >> q && q) {
        cout << phisum[q] << endl;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

const int N = 1000000;

int n;

int phi[N+10],prime[N+10],tot,ans;//phi储存的是欧拉函数 prime按次序保存了全部的素数 mark是素数标记，false意味素，true意味合

bool mark[N+10];

void getphi()

{

int i,j;

phi[1]=1;

for(i=2;i<=N;i++)//相当于分解质因式的逆过程

{

if(!mark[i])

{

prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。

phi[i]=i-1;//当 i 是素数时 phi[i]=i-1

}

for(j=1;j<=tot;j++)

{

if(i*prime[j]>N) break;

mark[i*prime[j]]=1;//确定i*prime[j]不是素数

if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数

{

phi[i*prime[j]]=phi[i]*prime[j];break;

}

else phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性

}

long long phisum[1000006];

int main(){

getphi();

for (int i = 2; i <= 1000000; i++) {

phisum[i] = phi[i] + phisum[i-1];

}

int q;

while (cin >> q && q) {

cout << phisum[q] << endl;

}

return 0;

}

URAL 1057 Amount of Degrees

August 03, 20152015-08-03hahaschoolLeave a comment

［等待填坑中］

//
//  URAL 1057.cpp
//  playground
//
//  Created by Adam Chang on 2015/08/03.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <bitset>

using namespace std;

unsigned int x = 0, y = 0, k = 0, b = 0;

unsigned int dp[33][33];//dp[depth][request numbers of 1]
void get_dp(){
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    dp[1][0] = 1;
    dp[1][1] = 1;
    for (int i = 2; i <= 32; i++) {
        dp[i][0] = 1;
        for (int j = 1; j <= 32; j++) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }
}

unsigned int get_ans(unsigned int a){
    unsigned int ret = 0;
    int hav = 0;
    for (int i = 31; i >= 0; i--) {
        if (a & (1 << i)) {
            if (k >= hav) {
                ret += dp[i][k-hav];
            }
            hav++;
        }
    }
    return ret;
}

bitset<32> b_to_bin(unsigned int n){
    vector<int> vec;
    while (n) {
        vec.push_back(n % b);
        n /= b;
    }
    bitset<32> bit;
    for (int i = 1; i <= vec.size(); i++) {
        if (vec[(int)vec.size() - i] == 1) {
            bit[(int)vec.size() - i] = 1;
        }else if(vec[(int)vec.size() - i] == 0){
            bit[(int)vec.size() - i] = 0;
        }else {
            for (int j = (int)vec.size() - i; j >= 0; j--) {
                bit[j] = 1;
            }
            break;
        }
    }
    return bit;
}

int main(){
    cin >> x >> y >> k >> b;
    get_dp();
    bitset<32> bitx(b_to_bin(x));
    bitset<32> bity(b_to_bin(y));
    cout << get_ans(bity.to_ulong()+1) - get_ans(bitx.to_ulong()) << endl;
    return 0;
}

// URAL 1057.cpp

// playground

// Created by Adam Chang on 2015/08/03.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <bitset>

using namespace std;

unsigned int x = 0, y = 0, k = 0, b = 0;

unsigned int dp[33][33];//dp[depth][request numbers of 1]

void get_dp(){

memset(dp, 0, sizeof(dp));

dp[0][0] = 1;

dp[1][0] = 1;

dp[1][1] = 1;

for (int i = 2; i <= 32; i++) {

dp[i][0] = 1;

for (int j = 1; j <= 32; j++) {

dp[i][j] = dp[i-1][j-1] + dp[i-1][j];

}

unsigned int get_ans(unsigned int a){

unsigned int ret = 0;

int hav = 0;

for (int i = 31; i >= 0; i--) {

if (a & (1 << i)) {

if (k >= hav) {

ret += dp[i][k-hav];

}

hav++;

}

return ret;

}

bitset<32> b_to_bin(unsigned int n){

vector<int> vec;

while (n) {

vec.push_back(n % b);

n /= b;

}

bitset<32> bit;

for (int i = 1; i <= vec.size(); i++) {

if (vec[(int)vec.size() - i] == 1) {

bit[(int)vec.size() - i] = 1;

}else if(vec[(int)vec.size() - i] == 0){

bit[(int)vec.size() - i] = 0;

}else {

for (int j = (int)vec.size() - i; j >= 0; j--) {

bit[j] = 1;

}

break;

}

return bit;

}

int main(){

cin >> x >> y >> k >> b;

get_dp();

bitset<32> bitx(b_to_bin(x));

bitset<32> bity(b_to_bin(y));

cout << get_ans(bity.to_ulong()+1) - get_ans(bitx.to_ulong()) << endl;

return 0;

}

15多校2-9/HDU 5308 I Wanna Become A 24-Point Master

July 23, 20152015-07-23hahaschool2 Comments

更新

根据出题人的回复，问题应该已经修复了，本文代码中的PATCH部分可以忽略。关于原来出现的问题的证明也已经失效，敬请留意。

题意

给出一个数字n，问你如果给你n个n，你要怎么样才能利用加减乘除运算给算成24呢？注意，没个数字只能使用一次，所有的数字必须都要用到。你要按照题里面介绍的特别的表示方法把你的解法表示出来。除法是可以出分数的，因为是SPJ，应该可以过。

思路

我个人不太认同出题人题解里面给出的手算4～15的所有情况，对于较大的数再机智得直接消除凑24，因为手算的太多了。

我的思路是对于比较小的情况，即n <= 27的时候，可以直接利用dfs找出答案。因为题目给出的表示方法其实意外地适合dfs的搜索过程，我们不断的枚举下一个操作，即从当前没用过的数里面选出两个，然后尝试加减乘除，每一次尝试就是改变当前数组尾部的值，同时做好标记进入下一层。只要搜索成功，我们就可以在dfs的退出过程中将路径保存下来，开一个stack，把这些个结果压进去，输出的时候弹出来，顺序就正好是正序了。

对于比较大的情况，事情就变得非常简单，假如说现在的n = k，那么只要找出24个相同的数k，加到一起，就是24 * k了，然后再额外拿一个k，做一下商，就得到了24，对于多出来的数，我们可以找两个k做一下差得0，然后用得到的0去乘上下一个多余的数，最后剩下一个0，和刚才的24加一下，多余的数也消耗掉了。

注意点

做这个题的时候发生了两处失误，首先是dfs的时候，范围设置的不正确，两层的循环都应该是从1开始的，原来外层从1开始而内层却是从i+1开始(i是外层的循环变量)，这样显然丢解了，而且搜索速度也拖慢了。

其次是题目中要求每个数只可以用一次，结果我偷懒把一个0跟好多哥数字去乘了，这样肯定就错了。

然后dfs应该采取一些必要的优化，比如说跳过重复的区段（剪枝），如果不做的话可能超时。如果实在没办法，打表也可以，反正才24种情况，并不会被拒绝提交。

然而还是没过

折腾了一下午后发现很有可能这个题的评测器在实现上有漏洞，通过排(feng)除(kuang)法(jiao)，发现有3组数据没有通过评测器，但是确实是正确的。

n = 13

1 + 2

3 + 4

5 + 6

7 + 8

9 + 10

11 + 12

13 + 14

15 + 16

17 + 20

21 - 22

18 / 23

19 + 24

n = 14

1 + 2

3 + 4

5 + 6

7 + 8

9 + 10

11 + 12

13 + 14

15 + 16

17 + 18

19 * 20

22 + 23

24 - 25

26 / 21

n = 22

1 + 2

3 + 4

5 + 6

7 + 8

9 + 10

11 + 12

13 + 14

15 + 16

17 + 18

19 + 20

21 + 22

23 + 24

25 + 26

27 + 28

29 + 30

31 * 32

33 + 34

35 - 39

36 / 40

38 / 37

42 - 41

如果数据确实不符合题意，请与我跟进，谢谢。

代码

为了过，最后没有办法特殊对待给上面三组数据打了补丁。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

int seq[100];
bool vis[100];
int n = 0;
struct expr{
    int a,b;
    char op;
    expr(int _a, char _op,int _b){
        a = _a;
        b = _b;
        op = _op;
    }
};
stack<expr> resstk;

bool dfs(int dep){
    if (dep == 2*n) {
        if (seq[dep-1] == 24) {
            return true;
        }else{
            return false;
        }
    }
    int prev = -909303;
    for (int i = 1; i < dep; i++) {
        if (!vis[i]) {
            if (seq[i] == prev) {
                continue;
            }else{
                prev = seq[i];
            }
            vis[i] = true;
            int inner_prev = -909303;
            for (int j = 1; j < dep; j++) {
                if (!vis[j]) {
                    if (seq[j] == inner_prev) {
                        continue;
                    }else{
                        inner_prev = seq[j];
                    }
                    vis[j] = true;
                    seq[dep] = seq[i] + seq[j];
                    if (dfs(dep+1)) {
                        resstk.push(expr(i,'+',j));
                        return true;
                    }else{
                        seq[dep] = seq[i] - seq[j];
                        if (dfs(dep+1)) {
                            resstk.push(expr(i,'-',j));
                            return true;
                        }else{
                            seq[dep] = seq[i] * seq[j];
                            if (dfs(dep+1)) {
                                resstk.push(expr(i,'*',j));
                                return true;
                            }else{
                                if (seq[j] != 0 && seq[i] % seq[j] == 0) {
                                    seq[dep] = seq[i] / seq[j];
                                    if (dfs(dep+1)) {
                                        resstk.push(expr(i,'/',j));
                                        return true;
                                    }else{
                                        vis[j] = false;
                                        seq[dep] = 0;
                                    }
                                }else{
                                    vis[j] = false;
                                    seq[dep] = 0;
                                }
                            }
                        }
                    }
                }

            }
            vis[i] = false;
        }
    }
    return false;
}
void init(){
    memset(seq, 0, sizeof(seq));
    memset(vis, 0, sizeof(vis));
    while (!resstk.empty()) {
        resstk.pop();
    }
}


void print(){
    while (!resstk.empty()) {
        expr &nowExpr = resstk.top();
        printf("%d %c %d\n",nowExpr.a,nowExpr.op,nowExpr.b);
        resstk.pop();
    }

}
void printSpec(){
    printf("1 - 2\n");
    int cur = n+2,pos = 3,zero = n+1;
    for (int i = 1; i <= n - 27; i++,pos++,cur++,zero++) {
        printf("%d * %d\n",zero,pos);
    }
    for (int i = 1; i <= 12; i++,pos+=2) {
        printf("%d + %d\n",pos,pos+1);
    }
    for (; cur <= 2*n-4;cur += 2) {
        printf("%d + %d\n",cur,cur+1);
    }
    printf("%d / %d\n",2*n-3,n);
    printf("%d + %d\n",2*n-2,zero);

}

int main(){
    while (scanf("%d",&n)!=EOF){
        if (n > 27) {
            printSpec();
            continue;
        }
        /*
         PATCH FOR THE DEFECTIVE SPJ
         */
        if (n == 22){
            printf("1 + 2\n"); printf("3 + 4\n"); printf("5 + 6\n"); printf("7 + 8\n"); printf("%d + 9\n",n+1);
            printf("%d / 10\n",n+2); printf("%d / 11\n",n+3); printf("%d / 12\n",n+4); printf("%d / 13\n",n+5);
            printf("%d * %d\n",n+6,n+7); printf("%d * %d\n",n+8,n+9); printf("%d * %d\n",n+10,n+11); printf("14 - 15\n");
            int now=n+13; for (int i=16;i<=n;i++){printf("%d * %d\n",i,now); now++;} printf("%d + %d\n",n+12,now); continue;
        }
        if (n == 13 || n == 14){
            printf("1 + 2\n");
            for (int i=1;i<=n*2-24;i++) printf("%d / %d\n",i*2+1,i*2+2); int num=n*4-46;
            int now=n+1+n*2-24;
            if (n!=12){
                printf("%d - %d\n",n+1,n+2); now++;
                for (int i=2;i<=n*2-24;i++){printf("%d - %d\n",now,n+1+i); now++;}
            }
            int k1=now;
            printf("%d - %d\n",num+1,num+2); num+=3; now++;
            for (int i=num;i<=n;i++){printf("%d * %d\n",i,now); now++;}
            printf("%d + %d\n",k1,now); continue;
        }
        /*
         END OF PATCH
         */
        if (n >= 1) {
            init();
            for (int i = 1; i <= n; i++) {
                seq[i] = n;
            }
            dfs(n+1);
            if (!resstk.empty()) {
                print();
            }else{
                puts("-1");
            }
            continue;
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

int seq[100];

bool vis[100];

int n = 0;

struct expr{

int a,b;

char op;

expr(int _a, char _op,int _b){

a = _a;

b = _b;

op = _op;

}

};

stack<expr> resstk;

bool dfs(int dep){

if (dep == 2*n) {

if (seq[dep-1] == 24) {

return true;

}else{

return false;

}

int prev = -909303;

for (int i = 1; i < dep; i++) {

if (!vis[i]) {

if (seq[i] == prev) {

continue;

}else{

prev = seq[i];

}

vis[i] = true;

int inner_prev = -909303;

for (int j = 1; j < dep; j++) {

if (!vis[j]) {

if (seq[j] == inner_prev) {

continue;

}else{

inner_prev = seq[j];

}

vis[j] = true;

seq[dep] = seq[i] + seq[j];

if (dfs(dep+1)) {

resstk.push(expr(i,'+',j));

return true;

}else{

seq[dep] = seq[i] - seq[j];

if (dfs(dep+1)) {

resstk.push(expr(i,'-',j));

return true;

}else{

seq[dep] = seq[i] * seq[j];

if (dfs(dep+1)) {

resstk.push(expr(i,'*',j));

return true;

}else{

if (seq[j] != 0 && seq[i] % seq[j] == 0) {

seq[dep] = seq[i] / seq[j];

if (dfs(dep+1)) {

resstk.push(expr(i,'/',j));

return true;

}else{

vis[j] = false;

seq[dep] = 0;

}

}else{

vis[j] = false;

seq[dep] = 0;

}

vis[i] = false;

}

return false;

}

void init(){

memset(seq, 0, sizeof(seq));

memset(vis, 0, sizeof(vis));

while (!resstk.empty()) {

resstk.pop();

}

void print(){

while (!resstk.empty()) {

expr &nowExpr = resstk.top();

printf("%d %c %d\n",nowExpr.a,nowExpr.op,nowExpr.b);

resstk.pop();

}

void printSpec(){

printf("1 - 2\n");

int cur = n+2,pos = 3,zero = n+1;

for (int i = 1; i <= n - 27; i++,pos++,cur++,zero++) {

printf("%d * %d\n",zero,pos);

}

for (int i = 1; i <= 12; i++,pos+=2) {

printf("%d + %d\n",pos,pos+1);

}

for (; cur <= 2*n-4;cur += 2) {

printf("%d + %d\n",cur,cur+1);

}

printf("%d / %d\n",2*n-3,n);

printf("%d + %d\n",2*n-2,zero);

}

int main(){

while (scanf("%d",&n)!=EOF){

if (n > 27) {

printSpec();

continue;

}

PATCH FOR THE DEFECTIVE SPJ

if (n == 22){

printf("1 + 2\n"); printf("3 + 4\n"); printf("5 + 6\n"); printf("7 + 8\n"); printf("%d + 9\n",n+1);

printf("%d / 10\n",n+2); printf("%d / 11\n",n+3); printf("%d / 12\n",n+4); printf("%d / 13\n",n+5);

printf("%d * %d\n",n+6,n+7); printf("%d * %d\n",n+8,n+9); printf("%d * %d\n",n+10,n+11); printf("14 - 15\n");

int now=n+13; for (int i=16;i<=n;i++){printf("%d * %d\n",i,now); now++;} printf("%d + %d\n",n+12,now); continue;

}

if (n == 13 || n == 14){

printf("1 + 2\n");

for (int i=1;i<=n*2-24;i++) printf("%d / %d\n",i*2+1,i*2+2); int num=n*4-46;

int now=n+1+n*2-24;

if (n!=12){

printf("%d - %d\n",n+1,n+2); now++;

for (int i=2;i<=n*2-24;i++){printf("%d - %d\n",now,n+1+i); now++;}

}

int k1=now;

printf("%d - %d\n",num+1,num+2); num+=3; now++;

for (int i=num;i<=n;i++){printf("%d * %d\n",i,now); now++;}

printf("%d + %d\n",k1,now); continue;

}

END OF PATCH

if (n >= 1) {

init();

for (int i = 1; i <= n; i++) {

seq[i] = n;

}

dfs(n+1);

if (!resstk.empty()) {

print();

}else{

puts("-1");

}

continue;

}

return 0;

}

标准答案里边很豪放地用了分数，正常来讲评测器应该是接受分数的，但不知道为什么不接受我这个调换位置保证不出现分数的答案了，真的很怪。我自己写了一个检查我自己答案的评测器，没有提供对分数的支持，但是评测器会在发现出现分数的时候报错，因为我的答案是已经调换顺序保证不出分数的了，此外也检查了每个数字的使用情况，保证和题意一致。

#include <iostream>
#include <cstring>

using namespace std;
int seq[200000];
int cnt[200000];

int main(int argc, const char * argv[]) {
    freopen("testdata.1009", "r", stdin);
    memset(seq, 0, sizeof(seq));
    int n = 0;
    while (cin >> n) {
        if (n <= 3) {
            int tmp;
            cin >> tmp;
            continue;
        }
        for (int i = 1; i <= n; i++) {
            seq[i] = n;
        }
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n-1; i++) {
            int a,b;
            char op;
            cin >> a >> op >> b;
            cnt[a]++,cnt[b]++;
            switch (op) {
                case '+':
                    seq[i+n] = seq[a] + seq[b];
                    break;
                case '-':
                    seq[i+n] = seq[a] - seq[b];
                    break;
                case '*':
                    seq[i+n] = seq[a] * seq[b];
                    break;
                case '/':
                    if (seq[a] % seq[b]) {
                        cout << "WRONG ANSWER AT " << n << endl;
                        return 998;
                    }
                    seq[i+n] = seq[a] / seq[b];
                    break;
                default:
                    break;
            }
        }if (seq[2*n-1] == 24) {
            for (int i = 1; i <= 2*n-2; i++) {
                if (cnt[i] != 1) {
                    cout << "WRONG ANSWER AT " << n << endl;
                    return 998;
                }
            }
        }else{
            cout << "WRONG ANSWER AT " << n << endl;
            return 998;
        }
        cout << "CORRECT AT " << n << endl;
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int seq[200000];

int cnt[200000];

int main(int argc, const char * argv[]) {

freopen("testdata.1009", "r", stdin);

memset(seq, 0, sizeof(seq));

int n = 0;

while (cin >> n) {

if (n <= 3) {

int tmp;

cin >> tmp;

continue;

}

for (int i = 1; i <= n; i++) {

seq[i] = n;

}

memset(cnt, 0, sizeof(cnt));

for (int i = 1; i <= n-1; i++) {

int a,b;

char op;

cin >> a >> op >> b;

cnt[a]++,cnt[b]++;

switch (op) {

case '+':

seq[i+n] = seq[a] + seq[b];

break;

case '-':

seq[i+n] = seq[a] - seq[b];

break;

case '*':

seq[i+n] = seq[a] * seq[b];

break;

case '/':

if (seq[a] % seq[b]) {

cout << "WRONG ANSWER AT " << n << endl;

return 998;

}

seq[i+n] = seq[a] / seq[b];

break;

default:

break;

}

}if (seq[2*n-1] == 24) {

for (int i = 1; i <= 2*n-2; i++) {

if (cnt[i] != 1) {

cout << "WRONG ANSWER AT " << n << endl;

return 998;

}

}else{

cout << "WRONG ANSWER AT " << n << endl;

return 998;

}

cout << "CORRECT AT " << n << endl;

}

return 0;

}

从1开始测了1个GB的数据，没发现问题，如果评测器有问题，请跟进，谢谢。

如果你还是不相信我

下面是官方题解：

虽然很蛋疼，写这么多其实就是为了让这么个玩意别再坑更多的人了。

POJ 2909 Goldbach's Conjecture

May 27, 20152015-05-27hahaschoolLeave a comment

題意

給你個數，讓你求出有多少種素數的組合使得兩個素數的和等於給你的這個數。數據範圍比較小，小於等於32768.

思路

沒啥好的數學辦法，但是數據範圍比較小，所以不妨嘗試打個素數表看看小於32768的素數有多少，打完了發現就3000多個，這樣的話即使是O(n^2)的時間複雜度也沒有問題。我們開個計數器數組，然後枚舉素數和，加到計數器上面，預處理好這些之後，直接受理查詢就可以了。

代碼

//
//  POJ2909.cpp
//  playground
//
//  Created by Adam Chang on 2015/05/27.
//  Copyright (c) 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

#define MAXN 32800

bool prime[MAXN];
vector<int> primels;
int cnt[MAXN];

bool isPrime(int n){
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

void genPrime(){
    memset(prime, true, sizeof(prime));
    for (int i = 2; i < MAXN; i++) {
        if (prime[i]) {
            if (isPrime(i)) {
                for (int k = 2; k * i < MAXN; k++) {
                    prime[k*i] = false;
                }
            }else{
                prime[i] = false;
                continue;
            }
        }else{
            continue;
        }
    }
}

int main(){
    genPrime();
    for (int i = 2; i <= MAXN; i++) {
        if (prime[i]) {
            primels.push_back(i);
        }
    }
    for (int i = 0; i < primels.size(); i++) {
        for (int j = i; j < primels.size(); j++) {
            if (primels[i] + primels[j] < MAXN) {
                cnt[primels[i] + primels[j]]++;
            }
        }
    }
    int q = 0;
    while (cin >> q && q) {
        cout << cnt[q] << endl;
    }

    return 0;
}

// POJ2909.cpp

// playground

// Created by Adam Chang on 2015/05/27.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

#define MAXN 32800

bool prime[MAXN];

vector<int> primels;

int cnt[MAXN];

bool isPrime(int n){

for (int i = 2; i <= sqrt(n); i++) {

if (n % i == 0) {

return false;

}

return true;

}

void genPrime(){

memset(prime, true, sizeof(prime));

for (int i = 2; i < MAXN; i++) {

if (prime[i]) {

if (isPrime(i)) {

for (int k = 2; k * i < MAXN; k++) {

prime[k*i] = false;

}

}else{

prime[i] = false;

continue;

}

}else{

continue;

}

int main(){

genPrime();

for (int i = 2; i <= MAXN; i++) {

if (prime[i]) {

primels.push_back(i);

}

for (int i = 0; i < primels.size(); i++) {

for (int j = i; j < primels.size(); j++) {

if (primels[i] + primels[j] < MAXN) {

cnt[primels[i] + primels[j]]++;

}

int q = 0;

while (cin >> q && q) {

cout << cnt[q] << endl;

}

return 0;

}

ZOJ 3558 How Many Sets III

February 02, 20152015-02-02hahaschoolLeave a comment

这个题很不错，卡了我半星期，再加上这个题没有题解，所以这次认真一些,因为不会LaTeX，这个题解写着挺吃力的。

题意
给定一个集合，这个集合的内容一定是{1,2,3,…,n}这个样子，要你求出这个集合的子集中，自成等差数列的有多少个。
举个例子，给出n=4，那么集合为{1,2,3,4},符合要求的子集有{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{2,3,4},{1,2,3,4},一共有9个，输出9就可以了。

AC做法
特别感谢cos65535的题解（日文）。cos65535さん、ありがとうございます！
这里我来说明一下这个做法，对于一个给定的n，一共有1～n-1这些可能的公差，对于每个公差a，形成的等差数列最多有（(n-1)/a)＋1项，也就是最多可以扣掉(n-1)/a个公差。扣掉b个公差的话，可以最多形成n-ab个等差数列。
在这里举个例子来说明这个，给出一个n=8，求公差为3的情况，那么可以算出对于8，可以扣掉最多2个3保证等差数列的起点不出界。扣掉一个3的时候，形成2项的等差数列，这个等差数列的终点最大为8，也就是{5,8}，把这个数列整个减1，这样就得到{4,7}{3,6}{2,5},{1,4}，一共是5个（8-1*3），同样地扣掉两个3的时候，形成3项的等差数列，终点最大为8，即{2,5,8}，像刚才那样整体减1，得到{1,4,7}，一共是2个(8-2*3).2+5=7,这个就是公差3的时候可以组成的等差数列数目了。
这个方法写成公式很简单，就是 $\sum_{a=1}^{n-1}\sum_{x=1}^{{floor}((n-1)/a)}(n-ax)$ 。
但是光有这个公式还不够，因为题目的数据范围是10^9,而上面介绍的那个做法是O(n^2)的时间复杂度，超时不可避啊。
优化需要两次，第一次是当公差一定时，我们可以用等差数列求和公式一次性求出来当前公差可以得到的当差数列数量。第二次是当我们使用完等差数列求和公式后，我们发现得到的式子中出现了n/a的形式，对于一定的n，a<=n,一共有sqrt(n)个n/a值（整数除法的特点），利用这一特点，我们可以只枚举1～sqrt(n-1)，我用这个范围枚举的是“最大可扣掉公差数目b”，对于给定的b，它适用于公差从(n-1)/b到(n-1)/(b+1)的情况，这里我们改造一下之前等差数列求和优化好的式子，再用一次等差数列求和。同时不要忘了我们的b值只枚举到了sqrt(n-1),每一次算出(n-1)/b其实就是对应的sqrt(n-1)以上的只对应一个公差的b值。

接下来上代码：

#include <cstdio>
#include <iostream>
#include <cmath>

using namespace std;

#define MODER 100000007

int main(){
    long long n = 0;
    while (scanf(" %lld",&n) != EOF) {
        long long res = 0;
        long long b = 1;
        for (long long a = n-1; b <= sqrt(n-1);) {
            long long c = (n-1)/b - (n-1)/(b+1);
            //cout << a << '|' << b  << "~" << c << endl;
            res += n*b*c-((a+a-c+1)*c/2)*b*(1+b)/2;
            if(!(a==b)) res += n*a-b*a*(1+a)/2;
            res %= MODER;
            b++;
            a = (n-1)/b;
        }
        printf("%lld\n",res);
    }
    return 0;

}

#include <cstdio>

#include <iostream>

#include <cmath>

using namespace std;

#define MODER 100000007

int main(){

long long n = 0;

while (scanf(" %lld",&n) != EOF) {

long long res = 0;

long long b = 1;

for (long long a = n-1; b <= sqrt(n-1);) {

long long c = (n-1)/b - (n-1)/(b+1);

//cout << a << '|' << b << "~" << c << endl;

res += n*b*c-((a+a-c+1)*c/2)*b*(1+b)/2;

if(!(a==b)) res += n*a-b*a*(1+a)/2;

res %= MODER;

b++;

a = (n-1)/b;

}

printf("%lld\n",res);

}

return 0;

}

递推方法
感谢于济凡同学。
对于1～n这个集合的满足要求的子集数目，设定为f(n)，对于n－1这个数，小于等于它的数中可以整除它的数的数量设定为g(n)，我们有递推关系式f(n)=2f(n-1)-f(n-2)+g(n)
这里说明思路，{1,2,…,n}这个集合，我们可以看成是{1,…,n-1}这个集合组成的全部等差数列，加上{2,…,n}这个集合组成的全部等差数列，但是我们发现{2,…,n-1}这个集合的等差数列算了两次，我们要去掉一次，但是我们还是少了一种情况，就是以1开头，n结尾的等差数列数目，这个就是g(n)了。

#include<iostream>
#include<cmath>
using namespace std;

int f(int t)
{
    int counter=0;
    for(int i=1;i<=t;i++)
    {
        if(t%i==0)
            counter++;
    }
    return counter;
}

int ans(int n)
{
    if(n==1)
        return 0;
    else if(n==2)
        return 1;
    else
        return ans(n-1)*2%100000007-ans(n-2)%100000007+f(n-1)%100000007;
}

int main()
{
    int m;
    while(cin>>m)
    {
        cout<<ans(m)<<endl;
    }
}

#include<iostream>

#include<cmath>

using namespace std;

int f(int t)

{

int counter=0;

for(int i=1;i<=t;i++)

{

if(t%i==0)

counter++;

}

return counter;

}

int ans(int n)

{

if(n==1)

return 0;

else if(n==2)

return 1;

else

return ans(n-1)*2%100000007-ans(n-2)%100000007+f(n-1)%100000007;

}

int main()

{

int m;

while(cin>>m)

{

cout<<ans(m)<<endl;

}

另一种求等差数列个数的方法
感谢铲神。
已知等差数列的公差、最后一项和首项，藉由等差数列通项公式，我们可以求出可用的等差数列数量。 $\sum_{a}^{n-1}\sum_{b}\frac{b-a_{1}}{a}$ 其中 $a$ 是公差 $b$ 是最后一项 $a_{1}$ 是首项，现在是n^2的时间复杂度，接下来优化为下面的形式，为n的时间复杂度，但是怎么弄成sqrt(n)的复杂度我实在想不出来了。。。

#include <cstdio>
#include <iostream>
#include <cmath>

using namespace std;

#define MODER 100000007

int main(){
    long long n = 0;
    while (scanf(" %lld",&n) != EOF) {
        long long sum = 0;
        for (long long a = 1; a <= n; a++) {
            long long tmp =0;
            tmp += (1+n)*n/2;
            tmp -= (1+n%a)*(n%a)/2;
            tmp -= (1+a)*a/2*(n/a);
            cout << tmp;
            tmp /= a;
            cout << '~' << tmp << endl;
            tmp %= MODER;
            sum += tmp;
            sum %= MODER;
        }
        printf("%lld\n",sum%MODER);
    }
    return 0;
}

#include <cstdio>

#include <iostream>

#include <cmath>

using namespace std;

#define MODER 100000007

int main(){

long long n = 0;

while (scanf(" %lld",&n) != EOF) {

long long sum = 0;

for (long long a = 1; a <= n; a++) {

long long tmp =0;

tmp += (1+n)*n/2;

tmp -= (1+n%a)*(n%a)/2;

tmp -= (1+a)*a/2*(n/a);

cout << tmp;

tmp /= a;

cout << '~' << tmp << endl;

tmp %= MODER;

sum += tmp;

sum %= MODER;

}

printf("%lld\n",sum%MODER);

}

return 0;

}