UVA – 11426 GCD – Extreme (II)

题目链接

给数n,求出所有gcd(i,j) (i<j<=n)的和.

对两个互质的数i,j,即gcd(i,j)=1,给它们都添加一个因子2,则有gcd(2i,2j)=2. 于是有gcd(ki,kj)=k.
求出所有互质的数对,然后就能进一步求出题目所需要的结果了.

用欧拉函数求出i以内与之互质的数的个数,并打表记录s=i*j内所有的数对i,j的gcd和:
sum[i*j]+=j*phi[i]

最后弄个前缀和,就能快速查询结果了.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int phi[4000005];
long long sum[4000005];
void euler(int n){
  for(int i=2;i<=n;++i) phi[i]=i;
  for(int i=2;i<=n;++i){
    if(phi[i]==i){
      for(int j=i;j<=n;j+=i){
        phi[j]=phi[j]/i*(i-1);
      }
    }
    for(int j=1;i*j<=n;++j){
      sum[j*i]+=j*phi[i];
    }
  }
  for(int i=1;i<=n;++i){
    sum[i]+=sum[i-1];
  }
}

int main() {
  //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  int n;
  euler(4000000);
  while(cin>>n&&n){
    cout<<sum[n]<<endl;
  }
  return 0;
}

LightOJ – 1138 Trailing Zeroes (III)

题目链接

给一个整数Q(1<=Q<=10^8),求最小的N使N!的后缀有Q个0.

N!有多少个因子5,后缀就有多少个0,因为前面一定有足够多的因子2来与之相乘. 于是可以对N!求因子5的个数来确定后缀有几个0,求法可参考 阶乘分解

对N可确定一个范围,然后二分答案求解,注意最后得到的N,其5的因子个数可能是大于Q的.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int getCnt(int n){
    int cnt=0;
    while(n){
        cnt+=n/5;
        n/=5;
    }
    return cnt;
}

int main() {
  int T,kase=0;
  //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  scanf("%d",&T);
  while(T--){
     int Q;
     cin>>Q;
     int l=5,r=Q*5;
     while(l<r){
         int mid=(l+r)/2;
         if(getCnt(mid)<Q) l=mid+1;
         else r=mid;
     }
     printf("Case %d: ",++kase);
     if(getCnt(r)==Q) printf("%d\n",r);
     else printf("impossible\n");
  }
  return 0;
}

POJ – 1015 Jury Compromise

POJ 1015
f[i][j][k]:从前i个人中选j个人,辩控差为k时的最大辩控和

状态转移即在第i(i<=j)个阶段,要么选第i个人,要么不选第i个人.
其实是个01背包.
注意下标范围,防负数出现.
嗯...代码写得挫,先这样吧.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#include<cstring>
using namespace std;

int p[201], d[201];
int f[201][21][801];
int P, D, N, M;
int ans[21];

struct Path {
  int n, m, k, id;
} path[201][21][801];

void goBack(int n, int m, int k) { //状态回溯 
  int cnt = 0;
  while (path[n][m][k].id) {
    int next_n = path[n][m][k].n;
    int next_m = path[n][m][k].m;
    int next_k = path[n][m][k].k;
    if (path[n][m][k].id != path[next_n][next_m][next_k].id)
      ans[cnt++] = path[n][m][k].id;
    n = next_n, m = next_m, k = next_k;
  }
}

int main() {
  int kase = 0;
  while (cin >> N >> M && N&&M) {
    for (int i = 1; i <= N; ++i) {
      cin >> p[i] >> d[i];
    }
    P = 0, D = 0;
    memset(f,-1,sizeof(f));
    path[0][0][400].id=0;
    f[0][0][400] = 0;
    for (int i = 1; i <= N; ++i) {
      for (int j = 0; j <= M; ++j) {
        for (int k = -400; k <= 400; ++k) {
          if (j > 0 && k + p[i]-d[i] + 400 >= 0 && k + p[i]-d[i] + 400 <= 800 &&
              f[i - 1][j - 1][k + 400] != -1 &&
              f[i][j][k + p[i]-d[i] + 400] < f[i - 1][j - 1][k + 400] + p[i]+d[i]) {
            f[i][j][k + 400 + p[i]-d[i]] = f[i - 1][j - 1][k + 400] + p[i]+d[i];
            path[i][j][k + 400 + p[i]-d[i]].id = i;
            path[i][j][k + 400 + p[i]-d[i]].k = k + 400;
            path[i][j][k + 400 + p[i]-d[i]].m = j - 1;
            path[i][j][k + 400 + p[i]-d[i]].n = i - 1;
          }
          if (f[i - 1][j][k + 400] != -1 &&
              f[i - 1][j][k + 400] > f[i][j][k + 400]) {
            f[i][j][k + 400] = f[i - 1][j][k + 400];
            path[i][j][k + 400].id = path[i - 1][j][k + 400].id;
            path[i][j][k + 400].k = k + 400;
            path[i][j][k + 400].m = j;
            path[i][j][k + 400].n = i - 1;
          }
        }
      }
    }
    for (int k = 0; k <= 400; ++k) {
      if (f[N][M][400 + k] != -1 || f[N][M][400 - k] != -1) {
        if (f[N][M][400 + k] > f[N][M][400 - k]) {
          goBack(N, M, k + 400);
          P = (f[N][M][400 + k] + k) / 2;
          D = (f[N][M][400 + k] - k) / 2;
        } else {
          goBack(N, M, 400 - k);
          P = (f[N][M][400 - k] - k) / 2;
          D = (f[N][M][400 - k] + k) / 2;
        }
        printf("Jury #%d\n", ++kase);
        printf(
            "Best jury has value %d for prosecution and value %d for "
            "defence:\n",
            P, D);
        for (int i = M - 1; i >= 0; --i) {
          printf(" %d", ans[i]);
        }
        printf("\n");
        break;
      }
    }
  }
  return 0;
}

LightOJ – 1234 Harmonic Number

Harmonic Number

(有技巧的打表)

直接打表爆内存,隔50个打表还行.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

#define ll long long
using namespace std;
const int maxn = 1e8;

double H[2000000];
void getH(){
    int k=0;
    double res=0;
    for(int i=1;i<=maxn;++i){
        res=res+1.0/i;
        if(i%50==0) H[++k]=res;
    }
}

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int T, kase = 0;
  getH();
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    double ans=H[n/50];
    int t=(n/50)*50;
    for(int i=1;i<=n%50;++i){
        ans=ans+1.0/(t+i);
    }
    printf("Case %d: %.10lf\n", ++kase,ans);
  }
  return 0;
}

LightOJ – 1236 Pairs Forming LCM

Pairs Forming LCM

把n进行质因数分解,设n的某个质因子为p,其指数为cnt.
对i和j包含的相同质因子p,设指数分别为a,b,由于LCM(i,j)=n,则有cnt=max(a,b).
a,b共有2*(cnt+1)-1种方案(乘以2是a,b互换,减1是剔除a=b的重复情况)

之后由乘法原理,得到了(i,j)的方案数res, 但其中包括了i>j的部分.i<j 和 i>j是对称的, 则 (res+1)/2就是题目要求的了.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

#define ll long long
using namespace std;
const int maxn = 1e7;
bool v[maxn + 1];
vector<int> prime;
void primes() {
  v[0] = v[1] = 1;
  for (int i = 2; i <= maxn; ++i) {
    if (!v[i]) {
      prime.push_back(i);
      for (int j = i; j <= maxn / i; ++j) {
        v[i * j] = 1;
      }
    }
  }
}

ll divide(ll n) {
  ll res = 1;
  for (int i = 0; i < prime.size(); ++i) {
    if (prime[i] > n) break;
    int t = 0;
    if (n % prime[i] == 0) {
      while (n % prime[i] == 0) {
        t++;
        n /= prime[i];
      }
      res *= 2 * (t + 1) - 1;
    }
  }
  if (n > 1) res *= 3;

  return (res + 1) / 2;
}

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int T, kase = 0;
  primes();
  cin >> T;
  while (T--) {
    long long n;
    cin >> n;
    printf("Case %d: %lld\n", ++kase, divide(n));
  }
  return 0;
}

LightOJ – 1245 Harmonic Number (II)

LightOJ - 1245

整除分块裸题.

BZOJ 1257-余数之和里有应用过,推理部分也在那篇文章里,或者直接看《算法竞赛进阶指南》P139.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;

long long H( int n ) {
    long long res = 0;
    int len;
    for( long long i = 1; i <= n; i+=len ){
        len=n/(n/i)-i+1;
        res = res + (n / i)*len;
    }
    return res;
}

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int T,kase=0;
  cin>>T;
  while(T--){
      int n;
      cin>>n;
      printf("Case %d: %lld\n",++kase,H(n));
  }
  return 0;
}

LightOJ – 1282 Leading and Trailing

题目链接

要取出前三位数,可使n^k=a.bc*10^m, 则有klg(n)=m+lg(a.bc),接下来就简单了...

计算用log()涉及到换底,交上去过不了,应该是有误差.但用log10()可以,也是才知道还有log10()这个函数...

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;

int quickpow(int n,int m,int mod){
  int res=1;
  n%=1000;
  while(m){
    if(m&1) res=res*n%mod;
    n=(ll)n*n%mod;
    m>>=1;
  }
  return res;
}

int main() {
  //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  int T,kase=0;
  cin>>T;
  while(T--){  
    int n,k;
    cin>>n>>k;
    int a=quickpow(n,k,1000);
    double t=k*log10(n)-(int)(k*log10(n));
    int b=(int) (pow(10,t)*100);
    printf("Case %d: %d %03d\n",++kase,b,a);
  }
  return 0;
}

LightOJ – 1336 Sigma Function

题目链接

参考: https://blog.csdn.net/SSimpLe_Y/article/details/73804147

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;

int main() {
  int T,kase=0;
  cin>>T;
  while(T--){  
    ll n;
    cin>>n;
    ll ans=n-(int)sqrt(n)-(int)sqrt(n/2); 
    //sqrt(n)求n以内的完全平方数个数,1,4,9,16可以映射成1,2,3,4,这样就很明白了
    printf("Case %d: %lld\n",++kase,ans);

  }
  return 0;
}

LightOJ – 1341 Aladdin and the Flying Carpet

题目链接

因为有4000个case, 直接累计约数的话会超时,每个case的复杂度达10^6.

用算术基本定理的推论,则要先质数打表,不然对每个数进行质因数分解时还要一边求质数,会造成很多不必要的循环(质数之间有很多间隔).

奇怪的是后面剔除宽为1~b的时候,复杂度应该也为10^6,这样却不超时了.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;

int v[1000005];
int p[1000005];
int k;
void primes(int n){
  for(int i=2;i<=n;++i){
    if(v[i]) continue;
    p[++k]=i;
    for(int j=i;j<=n/i;++j) v[i*j]=1;
  }
}

ll divide(ll n){
    ll res=1;
    for(int i=1;i<=k;++i){
      int t=0;
      if(n<p[i]) break;
      while(n%p[i]==0){
        n/=p[i];
        t++;
      }
      res*=(t+1);
    }
    if(n>1) res*=2;
    return res;
}

int main() {
  int T,kase=0;
  cin>>T;
  primes(1000000);
  while(T--){  
    ll a,b;
    cin>>a>>b;
    ll ans=divide(a)/2;
    if(b>=sqrt(a)) ans=0;
    else{
       for(int i=1;i<b;++i){
         if(a%i==0) ans--;
      }
    }
    printf("Case %d: %lld\n",++kase,ans);

  }
  return 0;
}

HDU – 1260 Tickets

HDU 1260

又是一道简单DP...
轮到第i个人的时候,要么是单独一人买,要么是和前面一个人组团买.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;

int n;
int k;
int a[2005];
int b[2005];
int f[2005];
int main() {
  cin>>n;
  while(n--){
    cin>>k;
    for(int i=1;i<=k;++i){
      cin>>a[i];
    }
    for(int i=1;i<=k-1;++i){
      cin>>b[i];
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=k;++i){
      f[i]=min(f[i],f[i-1]+a[i]);
      if(i>=2) f[i]=min(f[i],f[i-2]+b[i-1]);
    }
    int s=f[k]%60;
    int m=f[k]/60%60;
    int h=f[k]/60/60;
    char state[]="am";
    if(8+h>12) state[0]='a',h-=12;
    printf("%02d:%02d:%02d %s\n",8+h,m,s,state);
  }
  return 0;
}