New Maths

題意：

定義一個(gè)不進(jìn)位的乘法運(yùn)算 ?，先給出一個(gè)n，判斷是否存在a，滿足a ? a = n
n的長度最多是25

題解：

17 * 17正常等于289
17 ? 17 =149
如果a的長度為x，那么最后得到的n的長度len是2x-1
倒著推就是：（len+1）>>1
n的位數(shù)小于等于25，所以a的位數(shù)一定小于等于13，直接暴力枚舉，然后判斷合理性
判斷依據(jù)：
逐位用 O(n) 求卷積某一位的方法求出 a ? a 每一位的結(jié)果，并與 n 對應(yīng)位進(jìn)行比較。
可以發(fā)現(xiàn)每一位的值，都是交叉相乘相加后取余，如果第3位，就是1×3，2×2，1×3(這里的1，2，3表示下標(biāo))。
至于為什么是交叉相乘相加得到？
額。。等我搞清為什么再更新

---

0427
突然想起這個(gè)題
參考文章
我們可以從前往后依次填充數(shù)字，然后對填的數(shù)字進(jìn)行運(yùn)算，判斷是否能完全對應(yīng)，因?yàn)槭菑那巴筇?#xff0c;所以答案一定是最小值

代碼：

#include <stdio.h> #include <iostream> #include <algorithm> #include <math.h> #include <string.h> #include <vector> #include <stack> #include <queue> #include <map> #include <set> #include <utility> #define pi 3.1415926535898 #define ll long long #define lson rt<<1 #define rson rt<<1|1 #define eps 1e-6 #define ms(a,b) memset(a,b,sizeof(a)) #define legal(a,b) a&b #define print1 printf("111\n") #define pb(x) push_back(x) using namespace std; const int maxn = 2e5+10; const int inf = 0x1f1f1f1f; const ll llinf =1e17+10; const ll mod = 1e9+7;int n,len; char s[maxn]; int a[maxn]; int b[maxn]; ll ans;bool check(int k) {int res=0;for(int i=1; i<=k; i++)res=(res+b[i]*b[k-i+1])%10;return res==a[k]; }void get_max() {for(int i=len+1; i<=n; i++)//判斷當(dāng)前數(shù)字是否與N相同{if(!check(i))return;}ll tem=0;for(int i=len; i>=1; i--)tem=tem*10+b[i];ans=min(tem,ans); }void dfs(int x) {if(x>len)//超過長度時(shí) 判斷是否滿足后面半段{get_max();return;}for(int i=0; i<=9; i++)//枚舉該位置上的數(shù)字{b[x]=i;if(check(x))//剪枝 將該位置填入i后 判斷此時(shí)得到的Bx是否和Nx相同 {dfs(x+1);}}}int main() {scanf("%s",s+1);len=strlen(s+1);ans=1e18;if(len%2==0)printf("-1\n");else{n=len;for(int i=1; i<=n; i++)a[n-i+1]=s[i]-'0';len=(len+1)/2;dfs(1);//從1開始枚舉位置printf("%lld\n",(ans==1e18)?-1:ans);}system("pause");return 0; } #include <map> #include <queue> #include <string> #include<iostream> #include<stdio.h> #include<string.h> #include <algorithm> #include <math.h> typedef long long ll; typedef unsigned long long ull; using namespace std; typedef pair<ll,ll> pii; #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define mem(a,x) memset(a,x,sizeof(a)) #define debug(x) cout << #x << ": " << x << endl; #define rep(i,n) for(int i=0;i<(n);++i) #define repi(i,a,b) for(int i=int(a);i<=(b);++i) #define repr(i,b,a) for(int i=int(b);i>=(a);--i) const int maxn=2e6+10; #define inf 0x3f3f3f3f #define sf scanf #define pf printf const int mod=10000; const int MOD=1e9+7;inline int read() {int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x; }vector<ll> m1; vector<ll> m2; priority_queue<ll, vector<ll>, greater<ll> > mn; //上 小根堆 小到大 priority_queue<ll, vector<ll>, less<ll> > mx; //下 大根堆 大到小 map<ll,ll>mp; ll n,m,p; ll ans=1e18; ll dis[maxn],vis[maxn]; ll a[maxn],b[maxn],c[maxn]; ll cnt,flag; bool check(ll num) {for(int i=0; i<=60; i++) c[i]=0;for(int i=1; i<=num; i++) {for(int j=1; j<=num; j++) {c[i+j-1]=(c[i+j-1]+b[i]*b[j])%10;}}for(int i=1; i<=num; i++) {if(c[i]!=a[i]) return 0;}return 1; } void dfs(ll num) {if(num==n+1) {if(check(n+n-1)) {ll p=0;for(int i=n; i>=1; i--) {p=p*10+b[i];}ans=min(ans,p);flag=1;}return ;}for(int i=0; i<=9; i++) { ///數(shù)字if(num==n&&i==0) continue;b[num]=i;if(check(num)) {dfs(num+1);}b[num]=0;} } int main() {string str;cin>>str;ll len=str.size();if((len+1)%2==1) puts("-1");else {for(int i=len,j=0; i>=1; i--,j++) {a[i]=str[j]-'0';}n=(len+1)/2;///數(shù)位dfs(1);if(!flag) puts("-1");else printf("%lld\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的New Maths的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。