算法入门【小q的数列】

Thinking Process

It's apparent to use recussion given the Recurssive formula.
The difficulty is how to get the minimum of n'.Thinking carefully,the formula like this:$f[i]=f[i\mathrm{/}2]+if[i]\; =\; f[i\; /\; 2]\; +\; i$%$22$ equals to $f[i]=f[i>>1]+if[i]\; =\; f[i\; >>\; 1]\; +\; i$%$22$.It's actually to get number of digit 1 in binary form. So the whole thing is definite now. We need a function to calculate number of 1 in bin form and calculate result sum that is represented 1....1 in bin form.

Code

#include<stdio.h>
#include<cmath>
typedef long long ll;
ll f(ll n) {
  if(n == 0) return 0;
  if(n == 1) return 1;
  return f(n / 2) + (n % 2);
}
ll d(ll n){
  ll cnt = 0;
  while(n) {
    if( (n & 1) == 1 ) cnt ++;
    n = (n >> 1);
  }
  int i = 0;
  ll res = 0;
  for( ; i < cnt; i ++) {
    res += pow(2, i);
  } 
  return res;
} 
int main() {
  int t;
  scanf("%d", &t);
  while(t --) {
    ll n;
    scanf("%lld", &n);
    printf("%lld ", f(n));
    printf("%lld \n", d(n));
    
  } 
}