Solution of Project Euler problems 20 and 26

My recent solution about problem 20 and problem 26 of Project euler

// Problem 20
// Simply implemenent an multiplication of big integer in C++
// and then calculate it

#include 
#include 

#define MAX 100
#define mod 10000
#define baselen 4
#define in(a) scanf("%d",&a)
typedef int type;
/////////////////////////////////////
struct bint{
        type dig[MAX], len;
        bint(){len = 0, dig[0] = 0;}
};


bool setNunmber(bint& a, char number[]){
        type i, j, w, k, p;
        char data[MAX*baselen+1];
        strcpy(data, number);
        w = strlen(data) - 1, a.len = 0;
        for(p=0;p<=w && data[p]=='0';p++);
        while(1){
                i = j = 0, k = 1;
                while(i=p){
                        j = j+ (data[w--] - '0')*k;
                        k *= 10, i++;
                }
                a.dig[a.len++] = j;
                if(w        }
        a.len--;
        return true;
}

void getAnsToString(bint& a, char ans[])
{
        type i;
        i = a.len - 1;
  char *p = ans;
        sprintf(ans, "%d", a.dig[a.len]);
  p += strlen(ans);
        while(i>=0)
  {
     sprintf(p, "%04d",a.dig[i--]);
     p += 4; 
  }
  sprintf(p, "%c", 0);
}



void by(bint a, type b, bint& c){
        type i, carry;
        for( i = carry = 0; i <= a.len || carry; i++){
                if( i <= a.len ) carry += b*a.dig[i];
                c.dig[i] = carry%mod;
                carry /= mod;
        }
        i--;
        while( i && !c.dig[i] )i--;
        c.len = i;
}

int main()
{
 bint product;
 char productInString[MAX*baselen+1];

 setNunmber(product, "1");
 for (int i = 2; i <= 100; ++i) by(product, i, product);
 getAnsToString(product, productInString);

 printf("%s\n", productInString);
 
 int total_digit = 0;
 for (int i = 0; i < strlen(productInString); ++i) total_digit += productInString[i] - '0';
 printf("Sum of the digit = %d\n", total_digit);

 return 0;
}

//Problem 26

#include 
#include 
#include 
using namespace std;
vector recurring_cycle;  //use to record the recurring_cycle

/*  use to record whether an remainder have ever appeard, since when 
 we find an remainder have already exist, we will know we find the 
 recurring cycle. remainder[n] record the first position after radix 
 point we encounter such remainder.
*/
int remainder[1000]; 
int ans_d; // record when will get the max length of recurring cycle
int maxlength = 0; // record the max length of recurring cycle
int main()
{
 for (int d = 2; d < 1000; ++d)
 {
  recurring_cycle.clear();
  memset(remainder, -1, sizeof(remainder));
  int current_remainder = 1;
  int position = 0;
  while (1)
  {
   if (remainder[current_remainder] != -1) 
   {
    /*Uncomment this part to see the recurring cycle
    printf("%d : ", d);
    for (int i = 0; i <= position - 1; ++i) printf("%d", recurring_cycle[i]);
    printf("\n");
    */
    if (position - remainder[current_remainder] > maxlength)
    {
     maxlength = position - remainder[current_remainder];
     ans_d = d;
    }
    break;
   }
   else remainder[current_remainder] = position;
   current_remainder *= 10;
   recurring_cycle.push_back(current_remainder / d);

   if (current_remainder >= d) current_remainder %= d;
   if (current_remainder == 0) 
   {
    /* For test purpose only
    printf("%d : ", d);
    for (int i = 0; i <= position - 1; ++i) printf("%d", recurring_cycle[i]);
    printf("\n");*/
    break;
   }
   ++position;
  }
 }
 printf("Max length of recurring cycle is %d, when d is %d\n", maxlength, ans_d);
 return 0;
}

[转]高达MS图鉴发行日期

第一卷2009年10月27日发售：UC篇VOL.1
收录作品
機動戦士ガンダム （TV）
機動戦士ガンダム 第08MS小隊 （OVA）
機動戦士ガンダム MSイグルー -1年戦争秘録- （OVA）
機動戦士ガンダム MSイグルー -黙示録0079- （OVA）
機動戦士ガンダム MSイグルー2 重力戦線 （OVA）

第二卷2009年11月发售：UC篇VOL.2
收录作品
機動戦士ガンダム0080 ポケットの中の戦争 （OVA）
機動戦士ガンダム0083 STARDUST MEMORY （OVA）
機動戦士Ｚガンダム （TV）

第三卷2009年12月发售：UC篇VOL.3
收录作品
機動戦士ガンダムZZ （TV）
機動戦士ガンダム 逆襲のシャア （劇場版）
機動戦士ガンダムF91 （劇場版）

第四卷2010年1月发售：UC/FC篇
收录作品
機動戦士Vガンダム （TV）
機動武闘伝Gガンダム （TV）

第五卷2010年2月发售：AC/AW篇
收录作品
新機動戦記ガンダムW （TV）
新機動戦記ガンダムW Endless Waltz （OVA）
機動新世紀ガンダムX （TV）

第六卷2010年3月发售：CE篇
收录作品
機動戦士ガンダムSEED （TV）
機動戦士ガンダムSEED DESTINY （TV）
機動戦士ガンダムSEED C.E.73 -STARGAZER- （OVA）
機動戦士ガンダムSEED ASTRAY -RED FRAME- （PV）
機動戦士ガンダムSEED ASTRAY -BLUE FRAME- （PV）

第七卷2010年4月发售：正历/西历篇
收录作品
TURN Aガンダム （TV）
機動戦士ガンダム00 （TV）

如何在blogspot中贴代码

首先follow这里的指示

然后你会发现生产的代码会对< >产生错误的处理，你可以到这里进行text -> html entity的转换

最后如果还有其他问题，可以参见这篇文章

另外我觉得很还是不要自动换行比较好，所以可以在html模板的javascript中添加这句
SyntaxHighlighter.defaults['wrap-lines'] = false;

Begin to solve Project Euler problem (Problem 1, 8 and 88)

I heard about Project Euler for a long time, so today I have a try on them. I picked the problem 1, 8 and 88, the reason why I pick these problems is because digit 8 is lucky number in Chinese language.

Some might felt inappropriate to post the solutions on the blog, however there is an except from PE FAQS:

I solved it by using a search engine, does that matter?

That depends on your motivation for solving the problems. It probably means that you’ve missed out on some beautiful and hidden mathematics.

So I think it's ok to post the solutions here. Please don't look at these post if you want to spoil the solving experiences for yourself

Here come my solution:
Ｐｒｏｂｌｅｍ　１　and Ｐｒｏｂｌｅｍ　８　are
so simple, you can check my codes for detail

Ｐｒｏｂｌｅｍ　１

#include <iostream>
using namespace std;
int main()
{
    int sum = 0;
    for (int i = 1; i < 1000; ++i)
    {
        if (i % 3 == 0 || i % 5 == 0) sum += i;
    }
    cout<<sum<<endl;
    return 0;
}

Ｐｒｏｂｌｅｍ　８

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    char data[] = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
    int maxNumber = 0;
    for (int i = 0; i < strlen(data) - 4; ++i)
    {
        int temp  = 1;
        for (int j = 0; j <= 4; ++j)
            temp *= (data[i + j] - '0');
        if (temp > maxNumber) maxNumber = temp;
    }
    printf("%d\n", maxNumber);
    return 0;
}

Problem 88 is much complex than the above two, so I would try to explain my approach here:

After some thoughts, we could find out N = 2*k is a guaranteed solution, we could always get the answer with two factors 2,k and (k - 2) factors equal to 1.

And as 2^15 > 12000 * 2 =24000, we could conclude that we can at most have 15 factors greater than 1.

So what we need to is enumerate all the possible ways of these 13 factors, figure out their product, and then we can know the number of ones。 Hence, if we have x factors greater 1, the total number of factors, in other words k, would equal to (product -sum(f1 + f2 +.. fx) + x).

And then, we record the minimal N we found so far when the size equals to k at entry minK[k].

Finally, we find out all the distinct item from array minK, and sum them up.

This solution runs in about 0.5 seconds in my Dell D630 Laptop

Problem 88

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <set>

using namespace std;
int minK[12001];// minK[k] stores the minimal N found so far here
int factors[16]; // save the current factors

void findMinK(int product, int upperBound, int level)
{
    if (level > 15) return; // return if there are more than 15 factors
    int ones;
    for (int i = 2; i <= upperBound; ++i)
    {
        if (product * i > 24000) break; //return if the current product have 
        else ones = product * i;
        factors[level] = i;
        for (int j = 1; j <= level; ++j) ones -= factors[j];
        if (ones + level <= 12000 && product * i <minK[ones + level])
            minK[ones + level] = product * i;
        findMinK(product * i, 24000 / (product * i), level + 1);
    }
}

int main()
{
    set<int> nSet;
    nSet.clear();
    memset(minK, 1, sizeof(minK));
    memset(factors, 0, sizeof(factors));
    findMinK(1, 24000, 1);
    int answer = 0;
    for (int i = 2; i <= 12000; ++i)
        nSet.insert(minK[i]);

    for (set<int>::iterator iter = nSet.begin(); iter != nSet.end(); ++iter)
        answer += *iter;

    printf("answer = %d\n", answer);
    return 0;
}

第一篇

果然还是应该写一下blog，就当成找个地方来记载自己的生活和知识吧。 有时候突然会想把自己的一些想法和一些刚学习到的有用的知识， 但是却发现不知道应该发去哪里好，所以还是弄一下blog的，虽然以我的性格不知道能够坚持多久就是了。 Anyway, 还是试着写一下吧。

还有就是这个博客里面很可能偶然会出现全部用英文写成的文章。。这个大家看见不要奇怪。。这个不是为了装B或啥的，只是想试着在平时锻炼一下自己的写作水平，毕竟在外企工作每天都在和英文打交道，另外有些东西用英文描述会比较容易表达的比较清楚嘛~ 当然由于我的英文水平实在是不怎样。。那个单词， 语法， 表达错误之类的就是肯定会出现的了，大家就将就一下吧……

好吧，我就是那作为开始的第一篇，期待着一个美好的未来。

如何处理folder属性中看不到sharing选项的问题

今天在2003的VM上突然发现文件夹选项中的Sharing这个tab突然不见了，google了一下发现众说纷纭，发现主要有以下几个可能的解决方法。

1. 首先是文件夹视图中可能被选择了use simple sharing，要取消这个可以选择 Windows Explorer -> Tools -> Folder Option ->　Ｖｉｅｗ　，　然后拉到最下面，如果被选中了ｕｓｅ　ｓｉｍｐｌｅ　ｓｈａｒｉｎｇ，　那么取消掉。

２．如果还是不行，可以查看Ｃｏｎｔｏｒｌ　Ｐａｎｅｌ　-> Administrative Tools -> Service , 然后检查其中的Server 和 Workspace 两个服务是否被起来了， 没有就选中这些服务，并把他start起来。这样子大概就能解决了

3. 如果如果你还是不行……那么那么请继续自行Google吧……

这两个service的主要作用根据某论坛的说法主要如以下所示：

The 'server' service is needed for sharing.
'Workstation' service is needed for accessing shared folders.