2016.1.27試題描述 楊輝三角是形如如下的數字三角形： 111 12 1……現在想求出楊輝三角第N行的N個數中，有多少個數能被給定的質數p整除。輸入一行兩個空格隔開的整數N和p輸出輸出一個整數，表示第N行能被給定的質數p整除的個數輸入示例32輸出示例1其他說明對於60%的數據，N≤30，p≤1...
2016.1.27
| 試題描述 |
|
楊輝三角是形如如下的數字三角形： 1 1 1 1 2 1 …… 現在想求出楊輝三角第N行的N個數中，有多少個數能被給定的質數p整除。 |
| 輸入 |
| 一行兩個空格隔開的整數N和p |
| 輸出 |
| 輸出一個整數，表示第N行能被給定的質數p整除的個數 |
| 輸入示例 |
| 3 2 |
| 輸出示例 |
| 1 |
| 其他說明 |
| 對於60%的數據，N≤30，p≤1000，對於80%的數據，N≤1000，p≤1000，對於100%的數據，N≤〖10〗^9，p≤1000 |
然後就一個一個試唄
#include<iostream> using namespace std; int a[1005],e,ans; int main() { int n,p,b,ct; scanf("%d%d",&n,&p); b=n-=1; while(b) { a[++e]=b%p; b/=p; } for(int i=0;i<=n;i++) { b=i;ct=1; while(b) { if(b%p>a[ct]) {ans+=1;break;} else {ct++;b/=p;} } } printf("%d",ans); }View Code
然後果斷TLE
然後根據楊輝三角的對稱性，砍一半
#include<iostream> using namespace std; int a[1005],e,ans; int main() { int n,p,b,ct; scanf("%d%d",&n,&p); b=n-=1; while(b) { a[++e]=b%p; b/=p; } for(int i=0;i<(n+1)/2;i++) { b=i;ct=1; while(b) { if(b%p>a[ct]) {ans+=1;break;} else {ct++;b/=p;} } } ans*=2; if(n+1&1) { b=n/2;ct=1; while(b) { if(b%p>a[ct]) {ans+=1;break;} else {ct++;b/=p;} } } printf("%d",ans); }View Code
然並卵，依舊TLE
於是機智的我想到了構造
還想到了狀態壓縮
就是二進位某一位為1表示構造的數在p進位下該位上比n在對應位上大
#include<iostream> using namespace std; int a[105],e,ans; int main() { int n,p,b,ct; scanf("%d%d",&n,&p); b=n-=1; while(b) { a[++e]=b%p; b/=p; } for(int t = e-1 ; t >= 1 ; t-- ) { for(int i = ( 1 << t ) - 1 ; i >= 1 ; i-- ) { b=i;ct=a[t+1]; for(int j = t-1 ; j >= 0; j-- ) { if(1<<j&b) ct*=p-1-a[j+1]; else ct*=a[j+1]+1; } ans+=ct; } } printf("%d",ans); }View Code
AC後激動的我瞬間覺得我有做神犇的潛質
但我發現其他人的代碼都特短。。。
我方了
冷靜後，發現我傻*了
明明可以反著算。。。要知道根據盧卡斯定理構造模p不等於0的數有多簡單。。。
看了代碼瞬間就懂的
AC代碼：
#include<iostream> using namespace std; int e,ans=1; int main() { int n,p,b; scanf("%d%d",&n,&p); b=n-1; while(b) { ans*=b%p+1; b/=p; } printf("%d",n-ans); }View Code
