Jan 18

NEERC2005 - Joseph

Art of Science 0 Comments

NEERC2005主页在这里。

题目给定n和k，要求$\sum_{i=1}^n(k\mod i)$。

我们先找一下规律，发现与等差数列是有关系的。我们对于当前的i，令$p=k\mod i$，$q=\left\lfloor\frac{k}{i}\right\rfloor$。那么当i增大1时，如果q不变，p一定减少了q，那么将p一直减小到0，同时对这一段进行求和（用数列求和公式），同时i增大到下一段的开头。

详细情况见代码：

#include <cstdio>
#include <algorithm>

using namespace std;

int n,k;

__int64 sum(int a,int d,int n) {
  return (__int64)(2*a-d*n)*(n+1)/2;
}

int main() {
  freopen("joseph.in","r",stdin);
  freopen("joseph.out","w",stdout);
  scanf("%d%d",&n,&k);
  int i = 1,p,q,a;
  __int64 r = 0;
  while (i<=n) {
    q = k%i; p = k/i;
    if (p>0) a = q/p;
    else a = INT_MAX;
    r += sum(q,p,min(a,n-i));
    i += min(a,n-i)+1;
  }
  printf("%I64d\n",r);
  return 0;
}
Jan 18

求强连通分量的三种算法——Kosaraju, Tarjan, Gabow

Art of Science 1 Comments

就我所知，有三种时间复杂度为O(n)的方法可以求强连通分量，分别是Kosaraju、Tarjan和Gabow。

  1. Kosaraju
    算法的步骤为
    • 对图G进行DFS，并按照遍历完成的先后顺序进行标号。
    • 将图G中所有的边反向得到G'。
    • 对G'进行DFS，每轮DFS都选择编号最大的点最为当前的遍历树的根。
    • 最后，遍历得到的森林就是SCC的集合。
    该算法的优点在于，最后得到的节点是按照拓扑序组织好的，在求解2-SAT的过程中十分方便。
  2. Tarjan
    第一个求解SCC的算法，应用非常广泛，几乎任何和图的遍历有关的问题都可以套用Tarjan算法的思想（比如，求割点、桥、块等等）。
    在遍历时，对每一个节点定义时间戳，同时定义Low函数，含义为节点及其子孙通过非父子边的返祖边所能到达的最小时间戳。最后若Low函数等于其时间戳，则当前递归栈内存在一个SCC。
    代码如下：
    void dfs(int index) {
  low[index] = dfn[index] = cnt++;
  used[index] = 1;
  del[index] = 0;
  st[top++] = index;
  for (int i = last[index]; i!=-1; i = e[i].nxt)
    if (!used[e[i].y]) {
      dfs(e[i].y);
      if (low[index]>low[e[i].y]) low[index] = low[e[i].y];
    }
    else if (!del[e[i].y]) if (low[index]>dfn[e[i].y])
      low[index] = dfn[e[i].y];
  if (low[index]==dfn[index]) {
    do {
      root[st[--top]] = index;
      del[st[top]] = 1;
    } while (st[top]!=index);
  }
}
  3. Gabow
    算法的原理说起来太麻烦，还是直接给出代码。其实这个算法并不是很常用。
    #include <cstdio>
#include <cstring>
#include <stack>

using namespace std;

const int MAXN = 1000;

struct node {
  int tar;
  node *nxt;
  node(int _tar,node *_nxt)
    : tar(_tar),nxt(_nxt) {}
};

node *g[MAXN];
int n,m,co,all,dfn[MAXN],id[MAXN];
stack<int> vec,path;

void dfs(int x) {
  dfn[x] = co++;
  vec.push(x);
  path.push(x);
  for (node *i = g[x]; i!=NULL; i = i->nxt)
    if (dfn[i->tar]==-1) dfs(i->tar);
    else if (id[i->tar]==-1)
      while (dfn[path.top()]>dfn[i->tar]) path.pop();
  if (path.top()==x) path.pop();
  else return;
  for (int i; ;) {
    id[i = vec.top()] = all;
    vec.pop();
    if (i==x) break;
  }
  all++;
}

int main() {
  freopen("gabow.in","r",stdin);
  freopen("gabow.out","w",stdout);
  scanf("%d%d",&n,&m);
  memset(g,0,sizeof(g));
  for (int i = 0,a,b; i<m; i++) {
    scanf("%d%d",&a,&b); a--; b--;
    g[a] = new node(b,g[a]);
  }
  co = all = 0;
  memset(dfn,-1,sizeof(dfn));
  memset(id,-1,sizeof(id));
  for (int i = 0; i<n; i++)
    if (dfn[i]==-1) dfs(i);
  for (int i = 0; i<n; i++)
    printf("%d\n",id[i]);
  return 0;
}
Jan 18

一首怪诞诗——《二倍距离》

Tiny Tricks 0 Comments

二倍距离

林亨泰

你的诞生已经
诞生的你的死
已经不死的你
的诞生已经诞
生的你的死已
经不死的你

一棵树与一棵
树间的一个早
晨与一个早晨
间的一棵树与
一棵树间的一
个早晨与一个
早晨间

那距离必有二倍距离
然而必有二倍距离的

你的诞生已经诞生，你的诞生已经诞生的你的死，已经不死的你的诞生，你的诞生诞生已经诞生的你的死，已经诞生的你的死已经不死的你……

一棵树与一棵树间的一个早晨，一个早晨与一个早晨间的一棵树……

那距离必有二倍距离，然而必有二倍距离的那距离必有二倍距离……

这首诗写了起点和终点，时间与空间。行文也深有循环不息的气味，确实引人深思。

没有终点。

Jan 17

POJ1091 - 跳蚤

Art of Science 0 Comments

完整的题目描述在这里。

题目给出了n和m，要求出满足最大公约数(x1,x2,...,xn,m)=1且xi不超过m的这样的x1,...,xn的组数。xi都是正整数。

如果n=1，那就是求欧拉函数$\varphi(m)$。我们可以联想其形式：$\varphi(m)=m\prod_{p|m}(1-\frac{1}{p})$。那么当n>1时我们也来类比一下相对应的公式。

令$\varphi(m,n)$表示题目中所要求的答案。我们发现，当m为素数时，$\varphi(m,n)=m^n-1$。这是显然的，因为除了(m,m,...,m,m)这一组数字以外，其余的都是可行的解。那么m不为素数时，我们把m的各个素因数分开考虑。如果某个素因数被n个数所共有，那么一共就少了$m^n\frac{1}{p^n}$种方案，考察m所有的素因数，我们得到$\varphi(m,n)=m^n\prod_{p|m}(1-\frac{1}{p^n})$。

至此，问题解决。

Jan 16

UVa10290 - {Sum+=i++} to Reach N

Art of Science 0 Comments

题目描述在这里。

题目的意思就是给定一个正整数n（n不超过9*1014），要求我们给出有多少种方式，使得n能够表示为若干个连续正整数的和。比如n=9，那么有3种方式：2+3+4，4+5，9。

我们可以假定a+(a+1)+...+(b-1)+b=n，也就是(b+a)*(b-a+1)=2n。而(b+a)+(b-a+1)=2b+1是一个奇数，说明(b+a)和(b-a+1)具有不同的奇偶性，必然有一个是奇数。我们先把n当中所有素因数2从等式两边约去，同时考虑到(b+a)和(b-a+1)奇偶性不同，就可以把问题转化为n的奇数约数有多少个。由于这里的a和b是不受n的限制的变量，我们只要得到一个奇数约数必然可以求出相应的a和b（注意到(b+a)-(b-a+1)=2a-1是一个正整数，所以(b+a)>(b-a+1)。）。比如n=12，给出一个奇数约数3，那么a=3，b=5；给出一个奇数约数1，那么a=b=12。

现在我们所要做的就是对n进行质因数分解，然后用各个素因数的指数求解。显然，O(n1/2)的算法是不够的。我们要具体考察一下素因数分解的过程。如果用[2,L]以内的素数进行分解，那么约去所有因数后，最后剩下的n'一定不含有该范围的任何质数，也就是说n'如果小于L2，那么一定是素数；如果大于L2，那么只需要判断n'到底是不是素数。我们注意到，如果n'不是素数且只含有两个素因数，我们是可以分析出结果的，也就是说，我们需要排除n'含有三个素因数的情况。注意到(105)3略大于9*1014，我们就找到了方法。

先预处理出[2,105]范围内所有的素数，并且对n进行分解。然后按照上面的方法对分解的结果n'进行讨论，关于判断n'是否是素数，我们可以用Miller-Rabin素性测试来解决，Java中可以借助BigInteger的isProbablePrime来判断。整个算法的复杂度约为O(n1/3)，下面就是代码，UVa上面的提交结果是运行了0.556s： 

import java.math.*;
import java.util.*;

class Main {
  private final static int MAXP = 100000;
  private final static long LIMIT = (long)MAXP*MAXP;
  private static int[] primes;

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    getprimes();
    while (in.hasNextLong()) {
      long n = in.nextLong();
      System.out.println(solve(n));
    }
  }

  private static int solve(long n) {
    if (n==0) return 0;
    while ((n&1)==0) n >>= 1;
    int ans = 1;
    for (int i = 0; i<primes.length; i++) {
      long t = primes[i];
      if (t*t>n) break;
      int cnt = 0;
      while (n%primes[i]==0) {
        n /= primes[i];
        cnt++;
      }
      ans *= cnt+1;
    }
    if (n==1);
    else if (n<LIMIT || BigInteger.valueOf(n).isProbablePrime(16))
      ans *= 2;
    else {
      long tmp = (long)(Math.sqrt(n)+1e-6);
      if (tmp*tmp==n) ans *= 3;
      else ans *= 4;
    }
    return ans;
  }

  private static void getprimes() {
    boolean[] isp = new boolean[MAXP+1];
    int size = 0,ptr = 0;
    for (int i = 2; i<=MAXP; i++)
      if (!isp[i]) {
        size++;
        for (int j = 2*i; j<=MAXP; j += i)
          isp[j] = true;
      }
    primes = new int[size];
    for (int i = 2; i<=MAXP; i++)
      if (!isp[i]) primes[ptr++] = i;
  }
}