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 mk<=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≤1050立宜，求出x在1~n的范圍中冷溃，滿足對(duì)所有的k都有mk<=x^k 的x有多少個(gè)者铜，答案9+7.簡(jiǎn)單說就是x和m的每一位兩兩比較x都大于等于m荷逞。例如n=72，m=4（m=04）.滿足的x為49,1419,2429,…,6469.共42個(gè)數(shù)字融击。
【分析】
typedef long long LL;
const LL Mod=1e9+7;
char s1[60],s2[60];int n[60],m[60];
LL bmp[60];//預(yù)處理不在邊緣上限時(shí)的方案數(shù)
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字符->數(shù)字疆液，個(gè)位放開頭
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;}
//比較兩數(shù)大小，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個(gè)9）有多少種方案
LL ans=0;
for (i=ln;i>=2;i--) {
//從高往低處理典予，（假設(shè)最高位到第i位填的數(shù)字二者都一樣）
if (n[i]>m[i]) ans+=(n[i]-m[i])*bmp[i-1]%Mod;
//第i位如果ni>mi,后面就按照填到999…9（i個(gè)9）方案即可
if (n[i]
//如果ni此時(shí)最高位到第i位二者一樣，后面再怎么填都>n
ans%=Mod;
}
if (n[i]>=m[i]) ans+=(n[i]-m[i]+1)*bmp[i-1]%Mod;
//個(gè)位處理一下
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.
【題目大意】
現(xiàn)在有一串序列乐严，序列中元素滿足一些性質(zhì)瘤袖。假設(shè)第i個(gè)元素為K，那么第i+1個(gè)元素L必須滿足L,K不互質(zhì)且L在之前的序列中沒有出現(xiàn)過麦备。在所有滿足上述兩個(gè)條件中的數(shù)中L是最小的孽椰。已知序列一開始為1,2,4,6,3…昭娩，問第n位是什么數(shù)字凛篙。
【分析】
值得注意的是，雖然n<=310^6,但不代表出現(xiàn)的數(shù)字就在這個(gè)范圍之內(nèi)栏渺。通過事后驗(yàn)證得知序列中最大的數(shù)達(dá)到了610^6.注意給出的初始序列呛梆，我們可以再往后拓展幾項(xiàng)：1,2,4,6,3,9,12,8,10,5,15,18,14,7… 明顯發(fā)現(xiàn)，當(dāng)序列中出現(xiàn)一個(gè)奇質(zhì)數(shù)p時(shí)磕诊，前一個(gè)必然2p填物。很容易得出這個(gè)結(jié)論，因?yàn)橹挥信cp不互質(zhì)才能使得p出現(xiàn)霎终，而又要最小滞磺，故肯定是2p。而之所以出現(xiàn)2p,之前的數(shù)一定與2p不互質(zhì)莱褒，而2p只能分解成2p击困，p又是在之后出現(xiàn)的，故之前肯定是一個(gè)偶數(shù)广凸，且所有與其不互質(zhì)的只有2p了（也即2,4,6…2*(p-1)都出現(xiàn)過）阅茶。而且蛛枚，可以得出，我們只要在質(zhì)因子上操作即可脸哀，因?yàn)橘|(zhì)因子不可再分解蹦浦，肯定是滿足最小條件。
先篩法求出質(zhì)數(shù)撞蜂，這里的范圍我們一開始給到310^6,發(fā)現(xiàn)RE盲镶，擴(kuò)大到8106通過。且事后發(fā)現(xiàn)最大數(shù)達(dá)到了6*106蝌诡，故預(yù)篩質(zhì)數(shù)還是有必要擴(kuò)大范圍的徒河。
在后，我們用num[i]=p表示第i個(gè)質(zhì)因子的1~p-1倍都已經(jīng)出現(xiàn)過送漠，如果下一個(gè)數(shù)是通過第i個(gè)質(zhì)因子達(dá)到不互質(zhì)這個(gè)條件顽照，那么下一個(gè)數(shù)可能就是p*第i個(gè)質(zhì)因子。我們將當(dāng)前序列中最后一個(gè)數(shù)進(jìn)行質(zhì)因子分解闽寡，枚舉是哪一個(gè)質(zhì)因子來作為前后二者的公因子（枚舉是哪一個(gè)質(zhì)因子的倍數(shù)作為下一個(gè)數(shù)）代兵，取這些候選數(shù)當(dāng)中的最小的就是序列中下一個(gè)數(shù)。
const long long M=8123456;
long long prime[M/8],no=0,num[M/8];
//prime[i]表示第i個(gè)質(zhì)數(shù)
//num[i]表示第i個(gè)質(zhì)數(shù)用到第幾倍
//no 表示質(zhì)數(shù)總個(gè)數(shù)
bool used[M],bin[M];
long long buc[M];
//used[i]表示數(shù)字i在序列中已經(jīng)出現(xiàn)過爷狈，bin[i]表示數(shù)字i是否是質(zhì)數(shù)
//buc[i]表示數(shù)字i是第幾個(gè)質(zhì)數(shù)
void _Prime(){//篩法求質(zhì)數(shù)
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作為初始序列植影，標(biāo)記為出現(xiàn)過
num[0]=prime[0]=1000000;//為next做準(zhǔn)備（）
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表示當(dāng)前最優(yōu)選擇是第next個(gè)質(zhì)數(shù)作為公因子
for(j=1;prime[j]*prime[j]<=now;j++)
//枚舉質(zhì)因子，這里優(yōu)化到根號(hào)即可
if(now%prime[j]==0){//prime[j]是一個(gè)質(zhì)因子
while(now%prime[j]==0)now/=prime[j];
while(used[num[j]*prime[j]]==1)num[j]++;
//存在某個(gè)數(shù)已經(jīng)用過而num數(shù)組未更新
if(num[next]*prime[next] > num[j]*prime[j]) next=j;//選第j個(gè)質(zhì)數(shù)作為公因子更優(yōu)
}
if(now!=1){//now還剩一個(gè)大質(zhì)數(shù)因子沒處理
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.
【題目大意】
總統(tǒng)選舉制度：超過半數(shù)的選民所選舉的被選舉人將獲得這個(gè)全體的所有選票涎永。例如思币，如果共7個(gè)州，每州5個(gè)市羡微，每個(gè)市4個(gè)選民谷饿，那么對(duì)于一個(gè)市只要獲得3張以上的選票，整個(gè)市的4張選票都?xì)w你所有妈倔。如果獲得了3個(gè)以上的市的選票博投，則整個(gè)州5個(gè)市的選票都?xì)w你所有，如果獲得了4個(gè)州以上的選票盯蝴，則此次由你當(dāng)選總統(tǒng)∫慊現(xiàn)在說明國(guó)家共有n個(gè)選民，只要n能被整數(shù)整除捧挺，就可以劃分成下級(jí)的行政機(jī)構(gòu)虑绵。比如130可劃分成1013，也可以劃分成5213闽烙，不同的劃分方案所需要的最低票數(shù)不同翅睛。130=1013，只要獲得6*7=42張選票即可當(dāng)選。（10中選6,13中選7）給出n,求出在所有可能的方案中最少獲勝票數(shù)為多少宏所。
【分析】
乍一看貌似分解質(zhì)因數(shù)即可酥艳，然后每個(gè)質(zhì)因子/2+1后累乘即可，但答案并非如此爬骤。例如64充石，若劃分成2^6,也即6級(jí)行政機(jī)構(gòu)，但每一級(jí)都得2個(gè)全部獲取才行霞玄，這種方案是最低票數(shù)是64骤铃。而若劃分成444，即3級(jí)行政機(jī)構(gòu)坷剧，每一級(jí)都獲得3張惰爬，即333=27。若劃分成88惫企，則只要55=25張即可撕瞧。所以64的答案是25.下面進(jìn)行數(shù)學(xué)推導(dǎo)。
假設(shè)p狞尔、q為兩個(gè)奇質(zhì)數(shù)丛版，考慮是否劃分的票數(shù)獲取。不劃分則要1+[pq/2],劃分則要(1+[p/2])*(1+[q/2]),[a/b]表示a/b下取整偏序。由于p,q都是奇數(shù)页畦，上式又可寫成(1+pq)/2 和 (1+p)(1+q)/4,作差，移到左邊有2pq+2-pq-p-q-1=pq-p-q+1=(p-1)(q-1)研儒，由于是奇質(zhì)數(shù)豫缨，p,q>=3,上式恒大于0，故如果存在奇質(zhì)數(shù)端朵，則拆分成質(zhì)因子相乘是最佳方案好芭。
如果存在質(zhì)因子2，需要單獨(dú)處理逸月。假設(shè)n可以寫成2k*q,其中k是n的2的因子個(gè)數(shù)栓撞。那么對(duì)于q仍然作質(zhì)因子分解處理遍膜，對(duì)于2k單獨(dú)處理碗硬。設(shè)f[a+b]表示2^(a+b)的最佳分配方案，枚舉a,找到最小的票數(shù)即可瓢颅。
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最優(yōu)分配方案
for(int i=3;i*i<=n;i++) {//分解質(zhì)因數(shù)
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];
}
