A. Street magic

【Description】

Ladies and gentlemen, David Blaine is back! Having realized that street magic is not as captivating to his audience as in the beginning of his career, David started having doubts about his capabilities. However, after giving it another thought he understood that math magic is the new trend in the entertainment industry. We all know David does not bother about easy stuff and he loves stunning the crowd, so he decided to do a famous, but not yet performed by anyone trick with tens. Here are the trick details. Two people from the audience pick an integer number each. Let's denote these numbers n and m. After that David calculates in his head the secret number x (it takes precisely 0.42 seconds). So what is so special about x? It is a positive integer number not greater n such that m^k<=xk for any k > 0. David found out that there could be very many such numbers, so he wants to know exactly how many exist for given n and m. Note: is modulo operation which finds the remainder after division of one number by another.

【Input】

The first input line contains two positive integer numbers n and m which were picked by the audience.

1 ≤ n, m ≤ 10^50

【Output】

The only output line should contain the number of possible secret numbers x modulo 1e9 + 7 for the given n and m.

【题目大意】

给n和m，n与m≤10^{50，求出x在1~n的范围中，满足对所有的k都有m}k<=x^k 的x有多少个，答案9+7.简单说就是x和m的每一位两两比较x都大于等于m。例如n=72，m=4（m=04）.满足的x为4_9,1419,24_29,…,6469.共42个数字。

【分析】

typedef long long LL;

const LL Mod=1e9+7;

char s1[60],s2[60];int n[60],m[60];

LL bmp[60];//预处理不在边缘上限时的方案数

int main(){

cin>>s1>>s2;

int ln=strlen(s1),lm=strlen(s2),i;

if(ln<<0;return 0;}

for(i=0;i

for(i=0;i

for (i=0;i

for (i=0;i字符->数字，个位放开头

int flag=0;

for(i=ln;i>=1;i--) {

  if(lm

  if(n[i]>m[i]) {flag=1;break;}

  else if (n[i]

}

if(flag==-1) {cout<<0;return 0;}

else if (flag==0) {cout<<1;return 0;}

//比较两数大小，n为0，n==m为1

bmp[0]=1;bmp[1]=9-m[1]+1;

for (i=2;i<=ln;i++) bmp[i]=bmp[i-1]*(9-m[i]+1)%Mod;

//前i位填到999…9（i个9）有多少种方案

LL ans=0;

for (i=ln;i>=2;i--) {

  //从高往低处理，（假设最高位到第i位填的数字二者都一样）

  if (n[i]>m[i]) ans+=(n[i]-m[i])*bmp[i-1]%Mod;

  //第i位如果ni>mi,后面就按照填到999…9（i个9）方案即可

  if (n[i]

  //如果ni此时最高位到第i位二者一样，后面再怎么填都>n

  ans%=Mod;

}

if (n[i]>=m[i]) ans+=(n[i]-m[i]+1)*bmp[i-1]%Mod;

//个位处理一下

cout<<ans%Mod<<endl;

return 0;

}

C. Crime fiction society

【Description】

The society of crime fiction lovers holds meetings every day since September 13, 1842. Each day a member of the society with the membership card number x gives a talk. After more than 150 years the society chairmen collected enormous data about presenters, and it was decided to analyze it. Turns out, on the first society meeting a talk was given by the member number 1, on the second meeting spoke the member number 2, on the third day – 4, on the fourth day – 6, on the fifth day – 3 and so on. The chairman noticed, that each day the membership card number of the presenter is equal to the minimal positive integer number that is not coprime with the membership card number of the previous presenter and is not equal to membership numbers of those who gave talks before. According to the tradition the card numbers of presenters were posted on the notice board, but in the Information Age the board was replaced with a digital screen. The society has bought software which computes the membership card number of the presenter on day n. However, the computation algorithm is very complex, so the society members is having doubts in its correctness. Could you please help them?

【Input】

The only input line contains a single integer number n, which is the number of the day for which you need to determine the presenter.

1 ≤ n ≤ 3 × 10^6

【Output】

Output the card number of the member who gives a talk on the n-th day.

【题目大意】

现在有一串序列，序列中元素满足一些性质。假设第i个元素为K，那么第i+1个元素L必须满足L,K不互质且L在之前的序列中没有出现过。在所有满足上述两个条件中的数中L是最小的。已知序列一开始为1,2,4,6,3…，问第n位是什么数字。

【分析】

值得注意的是，虽然n<=310^6,但不代表出现的数字就在这个范围之内。通过事后验证得知序列中最大的数达到了610^6.注意给出的初始序列，我们可以再往后拓展几项：1,2,4,6,3,9,12,8,10,5,15,18,14,7… 明显发现，当序列中出现一个奇质数p时，前一个必然2p。很容易得出这个结论，因为只有与p不互质才能使得p出现，而又要最小，故肯定是2p。而之所以出现2p,之前的数一定与2p不互质，而2p只能分解成2p，p又是在之后出现的，故之前肯定是一个偶数，且所有与其不互质的只有2p了（也即2,4,6…2*(p-1)都出现过）。而且，可以得出，我们只要在质因子上操作即可，因为质因子不可再分解，肯定是满足最小条件。

先筛法求出质数，这里的范围我们一开始给到310^6,发现RE，扩大到810^{6通过。且事后发现最大数达到了6*10}6，故预筛质数还是有必要扩大范围的。

在后，我们用num[i]=p表示第i个质因子的1~p-1倍都已经出现过，如果下一个数是通过第i个质因子达到不互质这个条件，那么下一个数可能就是p*第i个质因子。我们将当前序列中最后一个数进行质因子分解，枚举是哪一个质因子来作为前后二者的公因子（枚举是哪一个质因子的倍数作为下一个数），取这些候选数当中的最小的就是序列中下一个数。

const long long M=8123456;

long long prime[M/8],no=0,num[M/8];

//prime[i]表示第i个质数

//num[i]表示第i个质数用到第几倍

//no 表示质数总个数

bool used[M],bin[M];

long long buc[M];

//used[i]表示数字i在序列中已经出现过，bin[i]表示数字i是否是质数

//buc[i]表示数字i是第几个质数

void _Prime(){//筛法求质数

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

  if(bin[i]==0){

    prime[++no]=i;

    buc[i]=no;

    for(long long j=i;j<=8000001;j+=i)bin[j]=1;

  }

}

int main(){

_Prime();

used[1]=used[2]=1;//1,2作为初始序列，标记为出现过

num[0]=prime[0]=1000000;//为next做准备（）

long long n,i,j,k,now=1,next=2;

scanf("%I64d",&n);

if(n==1){printf("1");return 0;}

now=2;

for(i=1;i<=no;i++) num[i]=1;num[1]=2;

for(i=2;i

  next=0;//next表示当前最优选择是第next个质数作为公因子

  for(j=1;prime[j]*prime[j]<=now;j++)

  //枚举质因子，这里优化到根号即可

    if(now%prime[j]==0){//prime[j]是一个质因子

       while(now%prime[j]==0)now/=prime[j];

       while(used[num[j]*prime[j]]==1)num[j]++;

       //存在某个数已经用过而num数组未更新

       if(num[next]*prime[next] > num[j]*prime[j]) next=j;//选第j个质数作为公因子更优

    }

  if(now!=1){//now还剩一个大质数因子没处理

    j=buc[now];

    while(used[num[j]*prime[j]]==1)num[j]++;

    if(num[next]*prime[next]>num[j]*prime[j]) next=j;

  }

  now=num[next]*prime[next];

  used[now]=1;

  num[next]++;//更新num

}

printf("%I64d\n",now);

return 0;

}

E. Elections

【Description】

The President of Bandiaterra Mr. Barbato is preparing for the next year upcoming elections. Nowadays his rating has fallen drastically to the lowest value ever (0.42%). The staff of president administration office have realized that they have to act in order for Mr. Barbato to save his office. There are n citizens of Bandiaterra that are eligible to vote. Each of them is assigned to a particular electoral district. The electoral districts contain the same number of citizens each. The same principle is applied to split districts to subdistricts, subdistricts to subsubdistricts, subsubdistricts to subsubsubdistricts, etc. Splitting of an administrative unit (subdistrict) is allowed as long as the number of citizens in the unit is divisible by an integer. Traditionally there are two candidates for the president office: the current president and an opposition candidate. Each citizen of the smallest administrative unit votes directly for a delegate, which is obliged to vote for the respective candidate at the next state of the election. Thus, after several stages of the election each elective district (the largest administrative unit) is represented by a delegate, and these delegates give their votes to candidates. According to the Bandiaterra constitution, if the candidates have equal number of votes, the opposition candidate wins. Barbato was one of the election system's designers. For this reason, only the current president has the exclusive right to form the electoral districts. It means that Barbato is allowed to specify which citizens belong to which districts, as long as the numbers of the citizens in the districts respect the rules described above. Of course, Mr. President is going to hold a huge agitation campaign to convince the compatriots to vote for him. However, he would like to be sure that he will definitely be elected for a new term. Given that he decides on the structure of districts at all levels, what is the minimum number of votes that Barbato needs to guarantee his victory?

【Input】

The first line contains a positive integer number n — the number of citizens that are eligible to vote in Bandiaterra.

1 ≤ n ≤ 10^9

【Output】

Output a single line containing a single number — the minimum number of votes that would guarantee a victory for Barbato.

【题目大意】

总统选举制度：超过半数的选民所选举的被选举人将获得这个全体的所有选票。例如，如果共7个州，每州5个市，每个市4个选民，那么对于一个市只要获得3张以上的选票，整个市的4张选票都归你所有。如果获得了3个以上的市的选票，则整个州5个市的选票都归你所有，如果获得了4个州以上的选票，则此次由你当选总统。现在说明国家共有n个选民，只要n能被整数整除，就可以划分成下级的行政机构。比如130可划分成1013，也可以划分成5213，不同的划分方案所需要的最低票数不同。130=1013，只要获得6*7=42张选票即可当选。（10中选6,13中选7）给出n,求出在所有可能的方案中最少获胜票数为多少。

【分析】

乍一看貌似分解质因数即可，然后每个质因子/2+1后累乘即可，但答案并非如此。例如64，若划分成2^6,也即6级行政机构，但每一级都得2个全部获取才行，这种方案是最低票数是64。而若划分成444，即3级行政机构，每一级都获得3张，即333=27。若划分成88，则只要55=25张即可。所以64的答案是25.下面进行数学推导。

假设p、q为两个奇质数，考虑是否划分的票数获取。不划分则要1+[pq/2],划分则要(1+[p/2])*(1+[q/2]),[a/b]表示a/b下取整。由于p,q都是奇数，上式又可写成(1+pq)/2 和 (1+p)(1+q)/4,作差，移到左边有2pq+2-pq-p-q-1=pq-p-q+1=(p-1)(q-1)，由于是奇质数，p,q>=3,上式恒大于0，故如果存在奇质数，则拆分成质因子相乘是最佳方案。

如果存在质因子2，需要单独处理。假设n可以写成2^{k*q,其中k是n的2的因子个数。那么对于q仍然作质因子分解处理，对于2}k单独处理。设f[a+b]表示2^(a+b)的最佳分配方案，枚举a,找到最小的票数即可。

int main(){

long long n,ans=1,piao;

cin>>n;int k=0;

while(n%2==0){n/=2;k++;}

int f[40];f[0]=1;f[1]=2;f[2]=3;f[3]=5;//已知2,4,8分配

int p=4;long long i=16;

for(p=4;p<=k;p++){

    f[p]=i/2+1;

    long long tt=2;

    for(int j=1;j<=p/2;j++){

        f[p]=(1+tt/2)*f[p-j]

        tt*=2;

    }

    i*=2;

}

//处理2^i最优分配方案

for(int i=3;i*i<=n;i++)    {//分解质因数

    piao=i/2+1;

    while(n%i==0) {n/=i;ans*=piao;}

}

if(n!=1){piao=n/2+1;ans*=piao;}

cout<<ans*f[k];

}